Which shield to use for GPRS?
That library should work with pretty much anything that has the M10 module on it.

I only have experience with the SIM900 modules. Found the cheapest one on EBay.

While interfacing with these things can be a challenge at first, you really just need to read the manual for all the AT commands and execute them. I've written a couple of functions that may help:

Note: you may safely replace all instances of DEBUG_PRINT and DEBUG_PRINTLN with Serial.print and Serial.println.

SoftwareSerial SIM900(7, 8);

/*
    Sends AT commands to SIM900 module.

    Parameter   Description
    command     String containing the AT command to send to the module
    timeout     A timeout, in milliseconds, to wait for the response

    Returns a string containing the response. Returns NULL on timeout.

*/
String SIMCommunication::sendCommand(String command, int timeout) {
    SIM900.listen();
    // Clear read buffer before sending new command
    while(SIM900.available()) { SIM900.read(); }

    SIM900.println(command);

    if (responseTimedOut(timeout)) {
        DEBUG_PRINT(F("sendCommand Timed Out: "));DEBUG_PRINTLN(command);
        return NULL;
    }

    String response = "";

    while(SIM900.available()) {
        response.concat((char)SIM900.read());
        delayMicroseconds(500);
    }

    return response;
}

/*
    Waits for a response from SIM900 for &lt;ms&gt; milliseconds

    Returns true if timed out without response. False otherwise.
*/
bool SIMCommunication::responseTimedOut(int ms) {
    SIM900.listen();

    int counter = 0;
    while(!SIM900.available() &amp;&amp; counter &lt; ms) {
        counter++;
        delay(1);
    }

    // Timed out, return null
    if (counter &gt;= ms) {
        return true;
    }
    counter = 0;
    return false;
}