What's the simplest Linux capable board I could make at home?

I'd like to see this too, but my gut instinct is to say "maybe, but it's a lot of work". Even the smallest Linux distro is going to need around a megabyte of RAM to run. This means at least 30 or so additional pins for the RAM controller in the microcontroller, and a couple of big RAM chips.

One of the simplest architectures I know that has Linux for it is the Atmel AVR32 series of parts. The smallest, the AT32UC3A0128 comes in a relatively hacker-friendly 100-pin TQFP package. This is at least amenable to hand-soldering, unlike most of the OS-capable embedded microcontrollers that come in BGA packages. (the chips that have the little solder balls underneath them) You can get an idea as to the complexity of a circuit using that chip by examining the EVK1100 eval board.

Linuxstamp is probably your best bet. It's open and has the PCB drawings, schematics, etc available. But as far as doing it at home - probably not. There's some very fine pitches on some of the parts. You're welcome to try, but it seems like a fair bit of consternation to me.

The Nintendo DS is capable of running uCLinux. You can get a used one for cheap, the only peripheral you need to run Linux on it is a microSD adapter (can be had for $15 from dealextreme.com) and a microSD (small ones are basically free these days)