We have just bought a property too and were in the same situation as it had no gas.
We contacted Nation Grid and they sent out the paperwork which we completed and then they sent a engineer round to survey the site - check nearest gas supply, how much piping they would need and so on
We then sent of a payment and booked a date for them to come - there was about a 6 week waiting time to get the works done (maybe this was just due to xmas).
You then need to contact a gas supplier to actually connect the gas and start supplying you.
The cost reduces if you are willing to dig the trench yourself so bare that in mind if you are within a budget.