I did a wire upgrade for my house when I bought a Nest myself... To be honest it was pretty easy. The trickiest part was making sure I had a path for the wire, but I just followed the original one along. I went with... I think a 7 wire version. While we only have heat (and our furnace was also capable of fan separate but no line for that was run originally) I decided it was a little future proofing. Plus the price in wire was not that hugely different.
So, recommendations if you are going to do it yourself:
1) Figure out the path it will go and whether you need to do anything (drill holes, etc...) to follow it.
2) Measure out that path to figure out how much wire you need. Buy longer than that. If you have too much you can cut off extra. Also make sure there is extra by the heating unit. If you ever need a new one, the wires may not connect in the exact same spot. Too short... Back to the store.
3) Figure out how many wires you need in it. In case you want to do any future proofing.
4) Get your wire.
5) Run the wire.
6) Secure the wire so it does not move around.
7) Coil the excess wire by the heating unit and secure it in place.
Disconnect the old wires but be careful to note which one went to what.
9) Connect the new wires to your unit. I would recommend turning off power to the unit while doing so. Make note of what color you connect to what (preferably use the standard color patterns) and label then on both ends (heating unit side AND behind the thermostat).
10) Connect the wires to your thermostat.
11) Test it all out. Make sure every feature you wanted works. Some thermostats (like Nest) will show you how they think they are wired.
12) Once you are sure it all works you could remove the old wires, but if they are not in the way I would leave them (just note they are disconnected so some future person does not think they are useful).
Just some basic ideas.