This site gives an interesting brief history of the compass rose. It has apparently been appearing on maps since the 1300s.

http://www.gisnet.com/notebook/comprose.html

The expression ‘boxing the compass’, by the way, means to name all 32 points of the compass in correct order. It has come to figuratively indicate a state of confusion.