I'm level 30 now and have had Lydia as my companion since about level 5. I cannot really take her adventuring now as she gets pwned by very easy opponents, even though I have upgraded her armour and weapons to be similar to mine. It appears to me as if she is not levelling, or if she is, very badly.

Do followers level? If so do we know how? Is it better to change followers every so often so you get a new one at a higher level?

According to the official strategy guide all the companions in the game level when you level.

Even if you tell them to wait at home, they still level as you are out gaining more levels so that they are never far behind (levels) when you come back to get them.

Smith her some nice armor and weapons and she will keep up nicely. Not quite as well as you can, but the difference is huge.

Followers always have the same level as you. If you are level 10 then they are level 10. If you leveled to 11 then they'll become level 11 immediately.

Normally each follower has a preset ratio of different skills when they level up. e.g. Every time one follower level up he/she may gain several skill levels(depending on their level), maybe from level 10 to level 11 one will gain 10 skill points, then perhaps 10% of it goes to light armor, 50% of it goes to one handed, 20% of it goes to sneak, etc. Different followers have different ratio for their skills.

However, there's a bug in the game currently that makes the followers unable to gain skills when they(you) level up. So when you get to level 30, they'll also be level 30, but have the skill levels of level 10.
On PC you can fix this by using console commands(disable and enable), but on consoles you can only wait for the patch and hope Bethesda has addressed this issue.

funny because when i did this she got killed by 2 iron arrows form an orcish bow from a bandit thug, she was wearing legendary forged dragonbone armor btw.

they dont level with you, maybe in a later patch they will after they actually try to finish making the game.

Companions do level with you, but unfortunately a bug in the scrip prevents their skill to ever raise, thus a companion that you got early will remain weak forever (or at least until they fix the bug). Its best to get a new companion once the current one stop being useful. If you play in PC you can use console commands to se their stats and select the most useful follower. Open the console, click on your companion and type getav health to see their hp or [b]getav onehanded/b] to see their one handed combat ability.

Tested out disable/enable, then used getav to check stats n' stuff. They were still low.
I just end up using setav to get the stuff to a level a bit less than my own. Works well enough, if tedious.