Credits: This information in this guide was gathered by many dedicated Riders of Rohan beta testers, supplemented by Hytbold's chief architect at Turbine jwbarry, and made possible with the patient assistance of Turbine's fantastic QA team. As with any aspect of an online game, these details may change over time, so your feedback is greatly appreciated, too!
Special Note: Lunasa has also compiled most of this information in spreadsheet format. See the post below for a link.
Galuhad has written a Lua plugin to help you keep track of your progress rebuilding Hytbold on multiple characters. You can find out more about Hytbold Assistant at the LOTRO Interface site.
Short version:
Reach level 84 and do the quests To Hytbold (in your mailbox) and Welcome to Hytbold.
Do the quest Aiding the Eastemnet and five of its related quests every day to earn [Tokens of Hytbold] and raise your reputation standing.
Start rebuilding Hytbold and barter for your class's armour sets with the [Tokens of Hytbold] you earned (see the summaries below).
(Optional) Do the crafting resource instances.
(Optional) Complete deeds and barter for housing decorations.
(Optional) Finish rebuilding Hytbold, experience the end of the Eastemnet's story, and barter for class armour sets for your alts.
(Optional) If you're still doing dailies at this point, you can exchange your extra [Tokens of Hytbold] for [Silver Tokens of the Riddermark] on a 1 : 1 basis at any Eastemnet Miscellany Quartermaster.