A Level 5 unit is one that has 4 promotions. So you need to get a unit with over 15XP. He doesn't have to be in the city in question.
With Warlords it has been changed to a Level 6 unit, which requires 21 XP (I think). It's much harder to get now, although combining it with a military academy and great generals makes it more useful too. Many people have said they use their first great general to promote a unit to Level 6 just so they can be assured of building WP.
If you do get a unit promoted to the desired level early in the game, you should strive to protect him so you can build WP later. It sucks to take your best unit and use him for garrison or mop-up duty, but it's usually worth it to get the WP.