How to generate a GUID/UUID?

The answer provided by Paul Sasik above works, but is not a secure way of generating a UUID because of it's use of Math.Random(), which is not a cryptographically secure pseudo-random number generator.

One of two things should be done, either use Crypto.getRandomInteger() to generate the random integer or use the code below as a drop in replacement for the whole UUID generation routine:

Blob b = Crypto.GenerateAESKey(128);
String h = EncodingUtil.ConvertTohex(b);
String guid = h.SubString(0,8)+ '-' + h.SubString(8,12) + '-' + h.SubString(12,16) + '-' + h.SubString(16,20) + '-' + h.substring(20);

Sources:

• https://www.salesforce.com/us/developer/docs/apexcode/Content/apex_classes_restful_crypto.htm#apex_System_Crypto_getRandomInteger

• https://developer.salesforce.com/forums/ForumsMain?id=906F000000092N0IAI

After working with the code in techtrekker's link (in OP comments) and other resources I cobbled together a standalone, working class for generating GUIDs in Apex code:

Sample usage:

   if (acct.AccountUuid__c == null)
        acct.AccountUuid__c = GuidUtil.NewGuid();

Apex class:

global class GuidUtil {

    private static String kHexChars = '0123456789abcdef';

    global static String NewGuid() {

        String returnValue = '';
        Integer nextByte = 0;

        for (Integer i=0; i<16; i++) {

            if (i==4 || i==6 || i==8 || i==10) 
                returnValue += '-';

            nextByte = (Math.round(Math.random() * 255)-128) & 255;

            if (i==6) {
                nextByte = nextByte & 15;
                nextByte = nextByte | (4 << 4);
            }

            if (i==8) {
                nextByte = nextByte & 63;
                nextByte = nextByte | 128;
            }

            returnValue += getCharAtIndex(kHexChars, nextByte >> 4);
            returnValue += getCharAtIndex(kHexChars, nextByte & 15);
        }

        return returnValue;
    }

    global static String getCharAtIndex(String str, Integer index) {

        if (str == null) return null;

        if (str.length() <= 0) return str;    

        if (index == str.length()) return null;    

        return str.substring(index, index+1);
    }
}

The answers given already either don't use a cryptographically secure random number or don't conform to UUID v4 standards. Here is a class and test that does both.

/*
How to generate a version 4 GUID (random)

1. Generate 128 random bits
2. Set the version: Take the 7th byte perform an AND operation with 0x0f followed by an OR operation of 0x40.
3. Set the variant: Take the 9th byte perform an AND operation with 0x3f followed by an OR operation of 0x80.
4. Convert the data to hex and add dashes
*/

public class GuidUtil { 
    static List<String> hexMap = new List<String> {
        '0', '1', '2', '3', '4', '5', '6', '7', 
        '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
    };

    public static String NewGuid() {        
        String randomStringAsHex = EncodingUtil.ConvertTohex(Crypto.GenerateAESKey(128));

        String versionHexBits = randomStringAsHex.SubString(14,16); // 7th bit 
        String variantHexBits = randomStringAsHex.SubString(18,20); // 9th bit

        Integer versionIntBits = convertHexToInt(versionHexBits);
        Integer variantIntBits = convertHexToInt(variantHexBits);

        Integer versionShiftedIntBits = versionIntBits & 15 | 64;  // (i & 0x0f) | 0x40
        Integer variantShiftedIntBits = variantIntBits & 63 | 128; // (i & 0x3f) | 0x80

        String versionShiftedHexBits = convertIntToHex(versionShiftedIntBits); // Always begins with 4
        String variantShiftedHexBits = convertIntToHex(variantShiftedIntBits); // Always begins with one of 8,9,a,b

        String guid = randomStringAsHex.SubString(0,8) + '-' + randomStringAsHex.SubString(8,12) + '-' + versionShiftedHexBits + randomStringAsHex.SubString(14,16) + '-' + variantShiftedHexBits + randomStringAsHex.SubString(18,20) + '-' + randomStringAsHex.substring(20);        

        return guid;
    }

    static Integer convertHexToInt(String hex) {        
        Integer d0 = hexMap.IndexOf(hex.Substring(1,2));
        Integer d1 = hexMap.IndexOf(hex.Substring(0,1));

        Integer intval = d0 + (d1*16);
        return intval;
    }

    static String convertIntToHex(Integer intval) {
        // https://stackoverflow.com/a/13465128
        String hs0 = hexMap.Get(intval & 15); // i & 0x0f
        String hs1 = hexMap.Get(((intval >> 4) & 15)); //(i >> 4) & 0x0f        
        return hs1+hs0;
    }
}

And here is a test for it

@isTest
public class GuidUtilSpec {
    private static testmethod void GuidIsV4() {
      Pattern p = Pattern.compile('[\\w]{8}-[\\w]{4}-4[\\w]{3}-[89ab][\\w]{3}-[\\w]{12}');
      for(Integer x = 0; x < 100; x++) {
        Matcher m = p.matcher(GuidUtil.NewGuid());
        System.assert(m.matches() == true);
      }
    }
}