My desktop:
Q8200 4 cores @2.33Ghz
8GB DDR2 RAM
NVidia 9800GT
Runs Minecraft at about 700fps according to fraps- only 40 according to the minecraft's F3 debug screen.
My laptop:
Satellite L300
T3200 2 cores @ 2.00ghz
4GB RAM
Linux Mint 10 and Windows 7 dual boot
Intel Media Accelerator (forget the specific model)
is playable, but has huge drops in framerate during chunk updates (that is, while night is falling or dawn), as well as when generating new chunks. THe way it plays on my laptop, I wouldn't recommend getting a machine with specs less than that; however, my laptop is also like 3 years old and probably less powerful than most laptops you can get today.
Generally speaking minecraft's speed is more CPU-bound than GPU-bound (graphics) because the graphics aren't fancy or use shaders and all that. Another important concern could be Hard drive speed, but as long as you don't get a 5400RPM drive it should be fast enough, and I/O only becomes a problem if you explore a lot of the world and generate a large number of chunks.
