Base classes are base classes because they are assumed to be things that just about anyone can do, join, or become. That is why you are able to freely choose among them when selecting your next level.
Prestige classes are special classes that are not simply assumed to be things that just about anyone can do at the drop of a hat—they require special preparation and training that goes beyond just the one level-up. That is why they have prerequisites.
Templates aren’t classes at all; they aren’t assumed to be something anyone can just do. Instead, they are more like things that happen to people. Templates are the result of curses, magical transformations, great blessings, or whatever—when they aren’t just hereditary.
So gaining a template doesn’t generally happen when you level up—and they certainly aren’t something you can choose to have happen when you level up just because those are the benefits you’d like best from your level. Rather, they happen when they get applied—by curse, or disease, or ritual, or divine intervention, or whatever. (When they get applied, they basically count as if you were already higher level, which delays your next level-up.) Sometimes those are things you can control—the lich template is a prime example—or can attempt to have happen on purpose—think purposefully getting bit by a vampire or werewolf. But other times they are completely outside your control.
In all cases, if you are interested in gaining a template, you should speak with the GM about it. The appropriate thing for a GM to do is evaluate the template, decide if they want to allow it on a PC—some of them are bad ideas for PCs—and then work with the player to allow the situation necessary to apply the template to occur in the story. Sometimes that’s easy, other times it’s hard, and of course some times there just isn’t really a good way to work it in even if the template itself would be OK. But a GM should try, if at all possible (and, again, they deem the template itself acceptable), because it’s a great plot hook and offers fantastic opportunity for character development, plus it makes the player happy.
I have also known GMs to grant, as part of the story, the option of “leveling” into a template. In effect, something in the story has changed the character—or revealed something about the character—and they now have latent abilities they could tap into. It doesn’t happen automatically (and the player could choose not to, if there are other things they’d prefer to level into), but it’s a good way to handle things.
But as a word of caution, templates tend to be very problematic because they make you “count as” a higher level without actually being a higher level. You usually get some potent abilities for it, but you also tend to miss out on some important things a level would have otherwise gotten—hp, saving throw bonuses, skill ranks, feats, and so on are all delayed by the template. That can be very severe, and personally I tend to try to avoid them altogether as a result, both as GM and player. When a player comes to me looking to use a template, I usually try to either revise it to make it “+0,” that is, benefits and drawbacks in equal measure (and both kind of on the small side), or else turn it into a proper “level” to take, complete with hd, base saving throws, skill points, and so on (this works well with the “level into” concept above).