The basic idea is every kill you get you gain exp. Once you get the required exp you gain a level.

Next is the fun part. After you level a fallout 3ish menu pops up. You get 5 skill points(SP) to distribute to your skills. With your skills you unlock perks.

It happens somewhat like this:
Level gain
Level is 6
New perk unlocked: pocket change
Perk stored with the rest of your available perks
You pick a perk from your available perk list

Perks can either unlock a skill or add to your skill level.

I guess all these updates add something new to the table. ;)