Hedgehogs need alot of room space to run about in and as such either need access to either a play pen or have a large cage. There is some debate as to how big the cage has to be, however I would say get the biggest one you can afford and go from there. I keep mine in a nero 3 cage and a 3ft viv, however some people don't like wire cages, this is due to the fact that hedgehogs can climb and they do not have the best eyesight, so can fall and injure themselves, they prefer either viv's (if you have one you need to make sure it has lots of ventillation as the humidity will definatly rise and this can lead to fungal infections and respiratory problems for the hog. (In past experience you need at least 5 vents in a 3ftx2ftx2ft viv, alternatively replace the glass with doors with mesh in) or zoozone cages. It is again down to the individual hog, Igel
has never had or shown the inclination to climb so he is fine in either a wire cage or a viv!
Below is a picture of Ivy's cage and Igel's viv, they are about 100cm long, 50cm wide and the cage is 50cm high, the viv is 35cm high (in hindsight it should have been slightly higher) they both have nice big cages, she was originally in the viv, but as she is bigger than Igel, I made the decision to put her in the cage and him in the viv until I can get a viv made for her that is slightly bigger than the one I've got.
The Viv stack I made over the summer

Substrates
I personally keep my both my boy and girl on newspaper, but every one is different, I prefer paper as this is natural, and free :-).
I have heard some say that sawdust can get stuck to their undersides and can lead to urinary tract infections etc due to it causing a blockage. However it is totally up the the individual, if sawdust is used, it does need to be dust free. Other substrates include "yesterdays news" and fleecy cage liners.
I am in the process of making a viv for Ivy and a wooden house for both Ivy and Igel with a base in, inside this I will line it with a fleece and place shredded paper for them to sleep in. I am changing from my fleeces as I believe this will be better for them both.
To sleep in I prefer a wooden house like the one in the picture below and then I buy some cheap fleece blankets and cut them to size so they can make their own nests out of what they please. I am now converting all the fleece to shredded news paper instead.
I have also found that old fleece jackets and unwanted jumpers provide perfect bedding for them and they both love to roll up in them. Some people prefer fleece houses for their hogs and a link is provided in my links section to a person that makes houses for hogs :-), I have got two fleece pouches now, and these are perfect for travelling the hogs as they can be warmed prior to travelling and the hogs will stay nice and cosy and most of the time go to sleep!