In the earlier years of the United States Navy, every Naval sailing ship was required to have a cannon for protection. Cannons of the times required round iron cannonballs. The ship's master wanted to store the cannonballs such that they could be of instant use when needed, yet not roll around the gun deck. The solution was to stack them up in a square-based pyramid next to the cannon. The top level had one, the next had 4, the third level down had nine, the lowest had sixteen. Four levels would then provide a stack of thirty cannonballs. The only real problem was how to keep the bottom level from sliding out under the weight of the other fourteen cannonballs on top. To do this, they devised a small brass plate (a "brass monkey") with one rounded indentation for each cannonball in the bottom layer. Brass was used because the iron cannonballs would not rust to the brass monkey, but would have rusted to an iron one.

When temperature falls, brass contracts in size faster than does iron. As it got cold on the gun decks of the vessels, the indentations in the brass monkey would get smaller than the iron cannonballs they were holding. If the temperature got cold enough, the bottom layer would pop out of the indentations, spilling the entire pyramid over the deck. Thus, it was (quite literally) cold enough to freeze the balls off a brass monkey.

According to the Naval Historical Center of the U.S. Department of the Navy, there's no evidence that there was ever a device called a brass monkey:

The first recorded use of the term "brass monkey" appears to dates to 1857 when it was used in an apparently vulgar context by C.A. Abbey in his book Before the Mast, where on page 108 it says "It would freeze the tail off a brass monkey." (Source: Lighter, J.E. ed. Random House Historical Dictionary of American Slang. (New York: Random House, 1994): 262.)

It has often been claimed that the "brass monkey" was a holder or storage rack in which cannon balls (or shot) were stacked on a ship. Supposedly when the "monkey" with its stack of cannon ball became cold, the contraction of iron cannon balls led to the balls falling through or off of the "monkey." This explanation appears to be a legend of the sea without historical justification. In actuality, ready service shot was kept on the gun or spar decks in shot racks (also known as shot garlands in the Royal Navy) which consisted of longitudinal wooden planks with holes bored into them, into which round shot (cannon balls) were inserted for ready use by the gun crew. These shot racks or garlands are discussed in: Longridge, C. Nepean. The Anatomy of Nelson's Ships. (Annapolis MD: ]Naval Institute Press], 1981): 64. A top view of shot garlands on the upper deck of a ship-of-the-line is depicted in The Visual Dictionary of Ships and Sailing. New York: Dorling Kindersley, 1991): 17.

They do add the following:

"Brass monkey" is also the nickname for the Cunard Line's house flag which depicts a gold lion rampant on a red field. (Source: Rogers, John. Origins of Sea Terms. (Mystic CT: Mystic Seaport Museum, 1984): 23.)

So it appears that the more colorful theory of the origin of the phrase "cold enough to freeze the balls off a brass money" is a legend, similar to the myth that the word fuck is an acronym.

Source: U.S. Department of Navy, Navy Historical Center: http://www.history.navy.mil/faqs/faq107.htm