As a previous poster mentioned, because RN and RM service papers are online, often individuals are easier to research than soldiers.
1. Other ranks (RN) service records 1853-1923 are online - ADM139
2. Officers (RN) service records 1756-1917 are online - ADM196
3. Other ranks (RM) service records 1842-1936 are online - ADM159
4. Wills of RN seaman 1786-1882 are online - ADM48
5. Medal rolls - as is the case with the Army, some are published (and forum members have copies of many) and some are not, but all are available at TNA
6. Greenwich Hospital (equivalent to the Army's Chelsea Hospital) has useful records if researching a Naval pensioner. Entry books (ADM73) for the early Victorian period have been transcribed and are available on Kevin Asplin's site. Later entry books are of course at Kew.
http://britishmedals.net/kevin/greenwich.html7. Once you know what ships an individual served on and some dates, don't forget records of the ship's themselves.
Ship's musters will help you trace an individual down the years, but ship's logs will give you virtually a day-by-day account of where the ship was, what it was up to etc etc
For one of my naval ancestors, I have extracts from the ships logs. More detail than you could possibly wish for!!