To get a Paladin you'll need a Statue.
To get Spears, Swords, Axes and Archers you'll need the barracks.
To get Scouts, Light Cavalry, Mounted Archers and Heavy Cavalry you'll need the Stables.
To get Rams and Catapults you'll need the Workshop.
To get a Noble Man you'll need the Academy.
For further information, take a look at the
help pages.