As commonly used, the expression "Tell it to the Marines" indicates that the speaker finds a story highly unlikely if not an outright lie. The implication is that only a Marine would be so thick-headed as to believe it.
As the Marines themselves use it, however, it means the opposite -- that if a Marine verifies that a tale is true, then it must be so as Marines have been everywhere and seen everything. In this version the phrase is attributed to Charles II who received confirmation about a story involving flying fish from a colonel of a British Marine regiment who was present at the time. This account, however, is a work of fiction by novelist and former Marine W.P. Drury.
The general use is derived from an even earlier work of fiction, an anonymous 1806 novel entitled The Post Captain; or, The Wooden Walls Well Manned: Comprehending a View of Naval Society and Manners. In it, the character Captain Brilliant expresses his outrage at a tall tale passing for truth by saying, "You may tell that to the Marines, but I'll be d----d if the Sailors will believe it!"
http://www.nmm.ac.uk/faqs/ms1.htm
http://www.expage.com/gunnygdotcom