Linux on board without 3rd party modules. Where to start?
I understand that you want to know how to make a processor work with Linux without having so much trouble. I will give you an answer based on my experience, but that has always worked so far, since I believe it could be useful for you. Therefore, it is quite specific for one particular case, that you can copy or take as a reference for a different processor. If it is not what you look for, it is no problem :-)

When it comes to the software part, as some colleagues suggested, you would need a Linux Kernel that supports the chosen microprocessor or architecture, a way to Boot (like U-Boot) for the system and the file system. I will refer to the whole thing just as kernel from now on.

First of all, I recommend to use a tool that would automatically give you all the kernel to make it easy. I recommend Buildroot or Yocto/Poky. The following image shows a full kernel mapped into a Flash, so you get an idea. Instead of having to get each of the layers one by one, these tools give the complete stack at once for the chosen architecture.



If you can choose your microprocessor (of course it has to support Linux). I recommend to go with the AT91 family. It includes all the SAMA5Dx boards as well as AT91SAM9x5. They are some of the simplest processors that can run Linux. In this link you can see step by step how to get your full kernel with Buildroot. Remember that you can decide to boot the kernel from a Flash or from a SD card (or micro SD). Both methods are explained in the guide. 

Furthermore, these boards have an evaluation kit where you can check that your kernel works and you learn how to implement it in advance. You will have the schematics of the evaluation kit and PCB design guide to make it easier. Finally, as some others said, you would need enough RAM, but that is also shown in the schematics.

I do not know if the answer would be useful for you, but I thought it might be. You can always look for similar guides from other manufacturers or try to go with Buildroot for a specific processor from the beginning. Best of luck!

Sources:

AT91 Linux4SAM

Buildroot

Yocto/Poky