My five year old is playing with Tux Paint right now on my laptop and having an absolute blast... It's an open source drawing program made just for kids, and is available for all platforms (though obviously, works very well on Ubuntu). It lets him draw with various pen shapes and colors, and also put "stamps" on the drawing as well. There's actually a ton of stamp images and drawing options, and with each action, there's a corresponding silly sound. The dialog box in particular cracks Alex up - it makes a 'Bleh, bleh, bleeeh" sound when asking if he wants to make a new drawing, and every time it comes up he loses it in peels of laughter.
It also comes with a tuxpaint-config app which lets you set options like making both mouse buttons work the same, starting the app in full screen mode, making sure that all the saves make new images so nothing is lost, etc. All around it's very cool. I've had Alex play with other drawing programs before -in fact he likes to use my Nokia 770 to make drawings which we email to his Mom - but this is the first program that I've found which is totally hands off on my part, he's exploring and having a really great time, and can save his creations with a click. So great.