What makes a wheel spin? I don't fully grasp what makes a wheel much easier to move than to push a solid block. 
The pressure at the point of contact between a wheel and the ground must be pretty enormous compared to the pressure created by a block of same material and mass as the wheel. 
Friction is defined as the product of normal force exerted on the object and the coefficient of friction between the object and ground. So I assume that for two identical objects of infinite masses this parameter does not make any difference. 
Given these circumstances, I don't understand the physics behind it. Am I missing some other attributes of a wheel that makes it easier to move?
 A: Let's see if we can answer your question by drawing a free body diagram for these two objects.

From the picture we can see, that in order for body to move, external force must be greater than friction force. If objects have the same mass and are in identical surroundings, they will be equally hard to move. (iff torque would be zero!)
We must however note that forces are not collinear, thus torque is produced. 
Now let's focus on our second observation. Torque on a round object causes it to rotate. The same thing happens to object 2. 
If you imagine the rectangular object rotating around it's center of mass, you can see, that it's lower left corner is in the way of the ground. Therefore that part of the body acts on the ground and by Newton's 3rd law, the ground acts on the corner of the body. 
Since frictional force is dependent on normal force, which increases, it makes the block even harder to move.
(Note that if that normal force exceeds the weight of the object, it's COM will move in positive y direction by Newton's second law)
What happens with COM of a round object, when it rotates? It stays at exactly the same height, so any torque produced does not lift up our object, requiring work, nor does it 'add' to frictional force.
In short:
Objects having circular cross-section are easier to displace as torque resulting from non-collinear forces does not increase normal force on the object, which would yield to higher frictional force.
A: Friction is really empirical, and can't be analysed well from first principals. That is, most of our knowledge comes from experiment rather than theory.
Friction is a combination of combination of inter-surface adhesion, surface roughness, surface deformation, and surface contamination. wiki:friction
These all contribute, and it is easy to see how roughness contributes.  For a first step, we'll take a simple model where we focus only on roughness.
Consider the Rack and Pinion:
 
Actually first, lets consider two racks (the straight bar)  Put them together, teeth to teeth and push the top one. In order to move the upper block, we'll need to slide up all the teeth, lifting the upper block (this is work!) until it is clear of the lower teeth. This is our block analog, where the teeth-to-teeth interaction represents the friction due to roughness of real surfaces.  In this particular situation, think about how much easier it would be to simply lift the block, move it and put it down one tooth over than pushing it.
Now go back to the rack and pinion, and push the pinion (gear).  There are a couple of things we notice:


*

*The tip of the tooth at the bottom has an instantaneous velocity of 0. - it is not moving relative to the rack. 

*Assuming clockwise motion, the tooth that is to the left of the bottom one is pulling up and out of the rack.  That is, rubbing against the rack teeth is at a minimum, and we're avoiding the "tooth lock" of our block scenario.


Rolling minimizes sliding by changing the sliding forces between two surfaces to vertical forces of separation of two surfaces.  As we move to smoother surfaces, we reduce the surface roughness, but inter-surface adhesion (electrical, magnetic, vacuum and even possibly molecular bonding) is always a factor, as is deformation.  Contamination is always an issue as well - ask any kid with a skateboard about the face-plant they made due to tiny pebbles on the pavement.  
Once we add an axle, things become a bit more complicated.  There are two ways of mounting a wheel, you can rigidly fix it to the axle, and let the axle rotate in bearings or, you can fix the axle and let the wheel rotate around the axle. in a simple bearing, we'd have a steel rod going through the hole in the pinion gear.  This would bring us back to sliding friction.  But, modern bearings look like this:  

Which brings the bearing problem back to rolling friction.
A: Pushing a heavy block across the ground is going to be hard because as you say the frictional force between the block and ground is $F = \mu F_N = \mu mg$ and for a heavy block this is going to be a large force:

But suppose you split your block into two parts, and you put a layer of oil in between the two parts like this:

At the contact with the ground the friction $\mu_1$ is large, while at the oil layer between the two blocks the friction $\mu_2$ is very small because oil is a good lubricant. So now when you push the top block it's going to slide forward with very little force needed, while the bottom block is going to stay stationary relative to the ground.
Although it may not be immediately obvious this is exactly what happens with a wheel. The bottom block corresponds to the rim of the wheel and the top block corresponds to the axle. And in between the axle and wheel we have a layer of oil:

The friction between the wheel and the ground $\mu_1$ is high so the point of contact of the wheel with the ground doesn't slide. However the friction between the axle and the wheel $\mu_2$ is very low so the wheel slides easily relative to the axle. That means when we push on the axle the wheel rotates easily around the axle and rolls forward with very little force needed.
A: One simple way to put it is that you shouldn't compare rolling a wheel with sliding a box; you should rather either slide both, or roll both.
In the first case, there's simply no difference - imagine a car with blocked wheels. The work against friction is what makes it hard.
In the second case, in order to tip the box, you would need to lift its center of mass - for a cubic box, by $(\sqrt{2}-1)/2$ times its side length. By doing this, you must work against gravity and store the potential energy, which will then dissipate as the box falls on its other side. But in fact, you could as well just lift it by this amount + 1 millimeter, turn in the air, and put back - this expends the same energy, and the friction does not enter the picture at all! 
In fact, when you are rolling the box, the friction is your friend rather than enemy! It's very annoying to try to tip a box which is sliding. Indeed, if you are trying to lift the box by one lower corner and the opposite one is fixed, then the whole box is acting as a lever. Because of that, you don't need to apply the force equal to the full weight of the box, but rather, in the beginning, only half of that, and even less when you proceed tipping. 
So, even if friction coefficients are the same, you see that the friction plays two completely different roles - in one case, it obstructs sliding, but in the other case, it facilitates the matter by allowing you to create a simple machine. (In fact, there is a small price for that - if you imagine that the other side of the box is fixed in a hinge, there will some dissipation due to friction in that hinge. This is, essentially, the "rolling friction" everyone is talking about.)
The rest is fairly obvious: you want to reduce the constant $(\sqrt{2}-1)/2$ by creating a shape that you can tip by lifting its centre of mass as little as possible. By playing with regular polygonal shapes, as in the gif in the comments, you see that eventually, you get the round shape that you can constantly "tip" without lifting at all.
A: Some of the other answers are correct, but too high of a physics level to be appropriate to the question. This needs a low-tech answer.
First, consider how much easier it is to walk than it would be to drag yourself across the ground. The reason is because you're not dragging anything - you lift a foot up, you move it forwards, you put it down, and repeat. It's easy to move the foot in the air, and the foot on the ground is fixed in place, not dragging.
Every point around the outside of a wheel is like a foot - with a vast number of feet around the outside of the wheel. When the wheel is not moving, it's like it's standing on the one foot at the bottom. When the wheel rolls, a new is foot coming down in front while the old foot goes up in back. The feet don't drag on the ground, each foot just lifts up and goes over the wheel and comes down in front. Going up and down doesn't drag.
Theoretically there would be zero friction for a perfect wheel rolling on perfect ground, because nothing drags. However the wheel and ground aren't perfect - there are tiny bumps and the surfaces bend, so there is still a small amount of friction. This is called rolling friction. Rolling friction is tiny compared to dragging friction.
A: This is basically because rolling friction is much less than sliding friction. 
If you push the block across a distance, it slides (rubs) over making it more difficult for you to push. A lot of your expended energy is also wasted in the process. 
But on the other hand, when you push a wheel of the same mass, it doesn't slide or rub as much along the road as a solid block. Also, assuming most of the mass of the wheel is concentrated at it's rim, it's got a greater moment of inertia which keeps it going once set in motion. 
Moreover, when sliding, the block is subject to sliding friction which is much greater than rolling friction as in the case of our wheel. 

The pressure created on the point of contact between the wheel and the ground must be pretty enormous compared to the pressure created by the block, given that both the wheel and the block are made of the same material and they have equal masses.

In the case of the wheel, I agree that there will be more pressure on the ground but you don't have to feel that pressure. After all, the maximum permissible force of friction between two objects is given by $\mu_sN$ where  $\mu_s$ is the coeff. of static friction and $N$
 is the weight of the object. Clearly pressure isn't a factor here.
The conclusion drawn is a block is harder to push because you have to overcome the friction at all times while pushing because it slides while in the case of a wheel, we don't have to overcome friction because it rolls instead of sliding.
If there were no friction both the block and the wheel would be equally hard to push.

If we somehow managed to slide the wheel like the block instead of rolling it then it would also be equally hard to push because now both of them are sliding and as they have equal weights, they'll suffer the same sliding friction force as mentioned above.
Edit:
I felt like adding a bit on why is sliding friction greater than rolling friction in response to the comment below.
When a body slides over another, the bodies in contact rub during movement and it's this rubbing which impedes the motion. But in case of rolling friction the bodies in contact don't slide against each other but just deform a bit and sometimes the motion is also impeded (just a bit) due to adhesive forces.
We can see that in both cases motion is impeded but clearly sliding friction generates more resistance to motion.
A: For a long time I had been perplexed by this, and even when people would give explanations things just felt off about their explanations. 
Here's what I found was helpful for my own personal understanding. It's a little bit round-a-bout but I think it really helps. 
If I put a ball in space and throw it it goes straight:

If I tie it to a mass that's much heavier than it, it'll instead spin in a circle around it. 

And the same idea will happen if I connect two rocks of the same mass, and I give one end a push:

This, to me, is THE secret for rolling. If two masses are stuck together, when you push one (in the direction in the image) the second mass is pushed in the opposite direction. Just one tug gets it to rotate forever. 
Now we can easily turn this into our "wheel" by just adding more mass. I believe you're going to assume the system will have these special rotation properties if I add more blocks on opposite sides:
 
Now in fact the only thing that matters, as we've said, is that everything is the same mass and equal distances apart. Well I can in fact just connect all of the masses together, and then they'll be locked in place, forced to have the same behavior. If I do that, then I can end up with something that looks like this:

The key in getting a good intuition is thinking of your wheel as a bunch of rocks glued together. In this case, just by giving a single one of our "rocks" a push, we can get the entire thing to spin forever. We call this a fancy name "angular momentum," and I think often don't explain that it's just what happens to when things are "glued together," like in this example. 
When something obstructs one end of this spinning mass, the rest of still wants to move! So if your spinning mass hits a bump, it will pivot at that stopping point:

In the wheel case, little tiny changes in the shape of the ground are pushing against the masses that are stuck together, and as a result the top half moves while the bottom half doesnt. The advantage here over the previous case is that these little tiny bumps can be made so small that our wheel grips the ground like a gear and uses it to push off of. The losses due to friction with the gear are very small, relative to just pushing a flat rock on the ground (which has the entire surface area of the rock-to-ground contact locked like a gear, shown in Alexander's answer.) In the end, the key is that our masses being locked together allow us to turn linear inertia into "eternal spinning," if we have a very very flat contact with the ground (but some "interlocking" so we can push off of it), then we can efficiently turn this "eternal spinning" back into linear motion more efficiently!
Personally I think the wheel is around us so much it's hard to take a step back and wonder "what's so great about rolling?" But the reality is that it is a pretty "unnatural" and unintuitive thing, at least according to nature. It's easier to evolve legs than it is to evolve wheels. You need very particular conditions to get this effect to work, and I don't think just writing down some friction terms or L = r x p does one of mankind's greatest inventions any justice! 
A: For a flat block being pushed on a rough surface


*

*friction opposes block's motion

*it does work against the block.


Consider an ideal wheel of same mass  and $\mu$ as the block.


*

*friction opposes the wheels motion but in doing so it produces a torque that assists the roll. For a wheel starting from rest, this is precisely what gets the wheel rolling instead of sliding.

*the friction does no work since the point of contact is at rest wrt to ground.


These two stark differences make rolling easier than sliding.
As a corollary, making a wheel slide would be exactly as difficult as sliding a block.

fig. F is friction. Arrow indicates direction of roll.

In the real world, the work done by friction is non-zero as the wheel deforms to acquire flatness at the point of contact.
As a first approximation, we assume friction to be independent of surface area and stress, so yes, its same for an equivalent pair of a block and a wheel. In the real world, the stress produces strain at the surface of interaction thus changing the effective frictional force.
A: Making a ball roll is much easier than to make a block slide. And I think your question is that why is it so? 
If so then the answer is that there are two different types of friction acting. For a rolling ball the friction is called rolling friction and for sliding block the friction is kinetic friction. Rolling friction is much smaller than kinetic friction and hence it's easy to move a ball as compared to a block. 

You can read more about Rolling Friction over Wikipedia.
A: Really simple Matrix-inspired answer: THERE IS NO FRICTION with a perfect, solid wheel; on a perfectly smooth surface; (and with no axle)
The wheel does not slide to move, it rolls: The point of contact is a fulcrum, around which any force will cause the wheel to rotate.
Nothing slides at the point of contact - The atoms come together near-perpendicularly, then separate the same way - They never slide past each other.
Plus, as @Steven Sagona explained, the mass going up on one side of a wheel is perfectly counteracted by the mass going down on the other side, like an elevator counterweight.
So an ant could start a 2 tonne wheel rolling in this perfect theoretical situation, it would just be very slow to accelerate the wheel. But it sure couldn't slide 2 tonnes, round or square.
The real world is only slightly different - Frictional forces from rolling are minor and parasitic in nature, compared with sliding the same mass.
A: My light bulb moment that gave me insight into wheels was that the point of contact between the ground and the wheel is stationary. So friction between the wheel and the ground doesn't actually slow down the rolling motion. Friction between the wheel and the ground is actually helpful, which is why we use rubber tyres.
If you think of a wheel moving with speed v, then the bottom of the wheel where it touches the ground has speed zero and the top of the wheel has speed 2v. (Which is also why cars tend to shield the tops of their wheels for better aerodynamics.)
Here is a still from the end of this video from MIT [CC-by-NC-SA]

A: To move a mass (with equal properties as the wheel) you have to pull (or push) much harder than pulling to let the wheel rotate. Intuitively this is clear. But why?
Well, when you pull (push) a heavy mass over the underground, much friction is involved which is dissipated into heat. This causes the fact that you have to pull hard. You also give kinetic energy to this mass.
In the case of the wheel, no dynamic friction is involved (only static, which makes it possible for the wheel to rotate). When you pull (push) the wheel with a piece of rope tied to its center (or in the case of pushing just use your hands) you only have to give it kinetic energy and don't have to overcome the friction forces.
On smooth ice, both are equally easy (difficult) to push (when their masses are not infinite, in which case you'll never be able to push both of them)as long sliding occurs. The mass gets only linear momentum while the wheel linear as well as rotational.
A: A very interesting question, which has exited people for many generations.
Well, basically you need to compare kinetic friction force of wheel (when you push brakes in a car for example) with rolling resistance force of wheel when it spins freely :
$$ \frac{F_k}{F_{rr}} = \frac{\mu_k N}{\mu_{rr}N} = \frac{\mu_k}{\sqrt {z/d}} $$
Here,
$\mu_k$ - kinetic friction coefficient of wheel material.
$z$ - wheel sinkage depth, which depends on wheel material, construction and load.
$d$ - wheel diameter
So now you see that you can easily minimize rolling resistance force by minimizing sinkage depth or simply by maximizing wheel diameter. In such way you can control, adjust rolling resistance force. However for kinetic friction force you don't have such many control options - just one - to change wheel/block material or spit oil between surfaces.
So in the end you get
$$ \frac{F_k}{F_{rr}} > 1 $$
EDIT
Our roads are usually made from asphalt, which also decreases sinkage depth for tires. Try to ride your bike on beach sand, which has greater sinkage depth than asphalt - then you will feel the difference, that now pushing your bike forward is much harder.
A: A number of answers have touched on what I personally think feels is the intuitive answer, however I think this small example allows one to see it more easily.
Suppose we have a square wheel and a normal wheel. When we push on the square wheel to move it, it is pushing against friction so it is very hard to move. On the other hand, when you push on a wheel it pushes against friction, using the friction to move itself - brilliant! We no longer need to overcome friction.
But wait, can't you just roll a square wheel as well? Why is it harder than rolling the normal wheel?
When you roll a square wheel, you have to increase it's potential energy as you raise it in the air, then let it go which causes all that potential energy to be released, causing it to roll a 90 degree rotation. Note, that essentially all this potential energy is just "wasted" - you waste energy raising the square wheel into the air and then when you release it, the energy just goes into deforming the square wheel slightly. Some of your energy of course moved it forward but only a small amount, most of it was spent fighting against gravity.
So how can we stop wasting so much energy? Hmmm what if we increase the number of sides from 4 to 8? Ah ha, here we still need to raise the wheel off the ground and release it however the height we need to raise it is much smaller - every "step" (pushing the wheel over one corner) of the wheel requires far less effort to lift. From a purely mathematical standpoint one  might think "ok, it takes less energy per step, but now we need more steps to travel one full rotation - is this really more efficient?" The answer is actually YES it is!: By doubling the number of corners, the total number of "steps" in the rotation process doubles, but the amount of energy "wasted" in each step is MORE than halved. (I don't have a reference on the math for this nor have I done it myself, however I think one may find it fairly intuitive to envision - proper analysis would be good to check this result as it's entirely possible my intuition is wrong however).
The wheel of course takes this concept to infinity - after adding an infinite number of corners we no longer need to waste energy lifting and dropping the corners of the object over and over in order to roll it.
Now finally we've reached the last paradox - after thinking about this so long it feels as if it should take zero energy to move the wheel! However, recall that one needs to apply a force to increase the velocity of the wheel in the first place, which allows us to store energy in a wheel to keep it rolling. If a perfect wheel is accelerated on a perfect surface, it will continue rolling forever until acted on by another opposing force, similar to an object moving through outer space (again, no reference or math shown here - my intuition could be wrong and it would be more complete to double check this result). 
