Before unlocking mounts you need to do a quest at around level 20. The character you saw on one below 20, was probably a level 20 character on a secondary class.