It is popularly believed to refer to the 99th Regiment of Foot, well known for their smartness in the late 19th century. However, Thomas Hardy used "up to the nines" in the 1870s and Rabbie Burns used the phrase "paint nature to the nines" long before then to mean �perfectly'. Others claim it refers to the old plural for �eyes' which was �eyne' - still a common pronunciation in Scottish English usage. Thus it may have meant "dressed up to the eyes". Basically, no-one really knows for sure where it came from. As a matter of interest, the equivalent phrase in French is "se mettre sur son trente et un" - "get into your thirty-firsts", as it were. This seems to suggest that people there tend to get tarted up at the end of the month!
(Click
here for a web-page with the views of Michael Quinion, the noted etymologist and lexicographer on the topic.)