I'm kinda new in the whole Arduino stuff. Is it possible to connect Arduino Nano to GPS/GPRS shield? I need to keep the whole board as small as possible so that I can fit it in a shoe.
Sorry for noob question ;D
The Arduino Nano is still a normal Arduino, just small. So if the GPS/GPRS is a shield, then yes it can be connected to an Arduino Nano. Because the Nano is so small, it won't line up with a shield, but I assume you already understand this.
If you can assemble electronics, you might want to look at this blog about Interfacing Arduino with a Telit GM862 too.
Sparkfun sell a range of interesting GPS and GPRS modules
If you have a way to make PCB's you could make something smaller than a Nano. A Nano contains a USB interface which is only required while you are developing the programs, but is a waste of space in use.
HTH
GB