Quote Originally Posted by Truce View Post
You've got to give up some seals to the guy behind the counter. I believe the first promotion will run you 1000 seals. Should be the fellow right in the middle.
Note that getting to Sergeant takes a little more. It'll be listed as a certain amount of Seals, but when you try to turn them in, you'll get told you're not ready yet. You then have to do a quest to get Sergeant.