I'm currently trying to research my grandfathers naval service record. The more information you have the better. There are a couple of books on this subject - try amazon.
The national archives online service can be frustrating and you end up where you started at times.
The following should help:
Service - RN/ RM/ ARMY/ RAF
These could be on the rim of certain medals - WW1 War medal etc although the WW2 campaign medals and stars don't have this information.
Date of birth - certificate if possible
Date of death - certificate
You need to be able to prove a link to you - family birth certificates etc and you may be asked to provide copies.
The Navy charge Â£30.00 admin charge for the information and you have to fill in a form showing the next of kin details etc. The other services probably charge something similar