This “Dubya” nickname: How long has it been around? When was it first used in print?
Molly Ivins was the first person I heard use Dubya. Same for Shrub. Both nicknames go back at least to the time he first ran for governor in '94. However, Molly seems to recycle way more jokes than she writes on her own, so my guess is they were already making their way around Austin political circles when she first put them in her columns.
Personaly, couldn’t tell 'ya… though it took me longer than most to “get it”…
Sorry for the non-informative response, but I’m about six drinks in to the company christmas party…
No cite, but I’ve read several places that Molly Ivins, a syndicated columnist based at the Fort Worth Star-Telegram, gets credit for the nickname “Shrub”.
Do you suppose if his name had been George W. Shrub, everyone would call him Bush? Think about it. 
No, they would call him “seed,” and his father would be Bush.
Earliest I was able to find was from the Economist of October 29, 1994, in “A new clump of Bushes.” In reference to George W., the magazine explains it’s “pronounced ‘George Dubbaya,’ to show he is a real Texan despite his Yale pedigree).”