OpenEmbedded is a good place to go to get started. A lot of embedded products use ARM and other processors, so cross-compiling is a big deal. Buildroot is another resource for building custom linux kernels for small systems.
You can also find lots of manufacturers with Single Board Computers (SBCs) that have tools to do what you want - do a google search for "SBC Linux" and you should have a gold mine.
LinuxDevices keeps a pulse on the linux embedded community and you should find several good articles there that lead you to products or software to help you.
Debian has an embedded build, but I haven't explored that.
There are several books on embedded linux available if you want to go that route.
The GPS receiver simply connects to a serial or USB port, and present an NMEA stream of data, which you can parse with GPSD and several programs can access it through GPSD. It's a very simple text based format.
I've used regular PC motherboards, and Atmel AT91 processors for embedded systems (with GPS, cellular, etc). There's a lot of information out there right now, and it's not expensive to get into. If I were to start a new project, I'd look at the AVR32 processors from Atmel - they are very hobbiest friendly, and provide a lot of community support for linux on the AVR32 architecture. They provide free GCC compilers and significant framework and examples if you want to go the OS-less route and have a single program running on the processer as well.
Good luck!