I actually found it in AppWorld, but I would recommend setting up via computer online and then it will send you a link to download it via email. You can sign up via Sign Up Now FREE. No Strings. No Kidding.
Note that the picture they show of the blackberry interface is NOT what it looks like on the bold. It's much more like the android theme on the bold.
On a side note about Youmail, one reason I'm not 100% sold on it is the new vm update and notification. The only way I can get quick vm updates and not kill my battery is to turn off polling and have it notify my of a new message by sms, which seems to be where it searches to see if you have a new message and automatically downloads. I don't text much, so having to go in and delete the sms is just an added step for me.