There is lots of military information held in the National Archives at Kew but if you don't know the regiment you could be searching for ages. I have used the following:
- Pay and Muster Rolls in WO 12.
- Discharge Papers (assuming he didn't die in service) in WO 97.
- Pension details if he served long enough to qualify in WO 22 & WO 23.
Lots of regiments would have been posted abroad or in Ireland, which would have counted as a home posting, so that may be why he doesn't show up in the census.
Diana