According to A.Word.A.Day: "hotsy-totsy (HOT-see TOT-see), adjective, also hotsie-totsie" means "Just right; perfect" and was coined by Billy De Beck, cartoonist 1892-1942), famed for his comic strip 'Barney Google and Snuffy Smith'." (He also coined "heebie jeebies.") Though the word seems pretty obscure, it's had quite a lot of use through the years, possibly because it's fun to say.

The word was apparently most used in the late 1920s and early 1930s, after 1925 when "The Hotsy-Totsy Boys" (a name for Duke Ellington, Jimmy McHugh and Irving Mills) recorded "Everything Is Hotsy Totsy Now," written by Mills and McHugh. The song was also recorded by several other artists such as The Original Indiana Five and The California Ramblers, and Coon Sanders Nighthawks Orchestra. Various other musicians (including Bix Beiderbecke, Hoagy Carmichael, Jimmy Dorsey, Tommy Dorsey, Benny Goodman, and Gene Krupa), recorded with Mills, who managed Ellington, under the name "The Hotsy-Totsy Gang" from 1928 to 1930.

"Hotsy Totsy" without the hyphen, which seems to have disappeared early on, was the name of a wooden boat used by one Vic Kleisrath to win the 1930 and 1931 American Power Boat Association Gold Cup races. "The Hotsy Totsy Girls" was the name of the Aetna Life women's basketball team from 1928 to 1934.

"Hotsy Totsy" was the nickname of a character called Rosalie Totsy on Welcome Back, Kotter (which may have led to the number of porn sites using "hotsy totsy" or "hotzy totzy" as a more interesting way of describing a woman than merely "hot").

There is apparently a "Hotsy Totsy Hot Sauce" still on the market, a font called "Hotsy Totsy", a "Hotsy Totsy Club" in San Francisco, and a group of furniture designers using the name. Hotsy Totsy Pictures produced two short films "On Goldie Pond" (which won "best local short" at the Seattle Lesbian and Gay Film Festival 1999) and "Sex Ray." Those Darn Accordions even did a "Hotsy Totsy Polka" on their 1996 album "No Strings Attached."

Weirdly enough, though, the word is sometimes used to mean "unnecessarily complicated", as in the sentence "Stay away from hotsy-totsy sophisticated words" found in the Google cache of http://www.123sortit.com/bboards/bb2/messages/53.html or the Ian Dury song "Uneasy Sunny Day Hotsy Totsy" (lyrics at http://www.countrybumpkin.ndo.co.uk/uneasy.html).

Tem42 says re: hotsy-totsy: We always used it to mean fancy or snobbish, growing up. I don't know why..."

Sources: A.Word.A.Day 30 January 2002
http://www.redhotjazz.com/hotsytotsyboys.html
http://www.redhotjazz.com/hotsytotsy.html
http://www.cutwater.com/Woodies/Racing/hotsy_totsy.htm
http://hotsaucecatalog.com/hs1964.html
http://www.aetna.com/history/1931all.htm
http://www.isomedia.com/homes/beesting/Proj4/default.html
http://www.qttc.com.au/destination/goldcoast/manual/secure/gc-b8b.htm
http://www.barstar.com/cgi-bin/sfo_db/search.cgi?setup_file=details.setup.cgi&db_id=1321