The preposition on has a number of different meanings depending on the context in which it is used.
In the case of "On Her Majesty's Secret Service", on is
used to describe an activity or a state
- to be on business/holiday/vacation
- The book is currently on loan.
Let's look at the term to be on active service
Someone who is on active service is taking part in a war as a member of the armed forces.
In James Bond's case he is "On Her Majesty's Secret Service"
This usage is mainly British.
As Michael Harvey pointed out in the comments:
is used on official letters from British or Commonwealth government offices.
See Google images: On Her Majesty's Service envelopes
OHMS is the abbreviation for 'On Her Majesty's Service' or 'On His Majesty's Service'.
O.H.M.S also refers to a 1937 British comedy Film renamed You're in the Army now for American audiences. The 007 movie was probably a play on words.
In American English in service would certainly apply.
- in the armed forces