Each little space in the wood (right down to cell scale) is filled with stone. That's the what -- the how is a bit trickier. There are numerous web pages which give explanations:
http://www.mineralgallery.co.za/woodopal.htm
http://encyclopedia.thefreedictionary.com/Petrified%20wood
http://www.state.nd.us/ndgs/ndnotes/ndn3_h.htm
The mineral seems usually to be quartz, or silica. Silica dissolves in water under conditions of very high pressure as found deep underground. Water saturated with silica then moves about through the rock, and where conditions are just right, it may precipitate out into spaces in the rock (this is how flints form). Sometimes there is a bit of wood just waiting there in the mud.
More commonly, wood fossilises to coal, and little bits of twig-shaped coal can be found in many rocks -- for example, they are common along the south coast of the Isle of Wight near here in southern England. In more recent rocks (such as the Gault Clay under the Downs) you get little bits of actual wood -- in that case a hundred million or so years old.
I believe sometimes petrified wood is "unfinished" -- a log can be wood at one end, and stone at the other.
A similar process happens when mud or loose sand becomes petrified to shale or sandstone, together with any bones, footprints, animal burrows etc. Often the spaces between the grains are filled with calcium carbonate, or lime, making a limestone.
(cont...)