The (primarily British until the Austin Powers movies popularized it in the U.S.) meaning of "randy" is horny, lustful, or lecherous. A.Word.A.Day says the Scots meaning is rude or coarse and that it probably derives from obsolete Scots "rand' (to rant). (Other sources suggest derivation from Hindustani "randi-baz," or lecher.) The sexual meaning has been recorded as early as 1847.

In the U.S., "Randy" is a nickname for such names as "Randolph" and "Randall" (sometimes even "Miranda," but it's more commonly a male name than a female one). Every baby name database I've found says these names are of Old English origin, so it's surprising that the nickname is only used in the U.S. and not in England. (Perhaps the other meaning crowded out the use as a nickname, as it now may be doing in the U.S.) MerGirl's husband is named Randy (and is American), and tells stories about encounters in English pubs like the following:

Randy: Hi, I'm Randy.
Woman: Oh, are you now?