Depends on what material you want to use. Stone altar? Craft (masonry). Wood? Craft (carpentry). Iron? Craft (blacksmithing). Considering most altars are simply blocks or tables, they wouldn't be difficult to craft.
Knowledge (religion) to know what an altar (note spelling) to your God would require. Craft(carpentry) to build a wooden altar, Craft(stone) to build a stone one. If you don't have a craft skill but you make the religion check (which shouldn't be hard, probably a DC10) you can probably make a makeshift altar out of basic materials at hand.
Profession Priest?