The little teeny tiny trees are, indeed, bonsai. The bon part refers to the tray that these things are normally grown in and the sai part means to plant.

Bonzai is, at least supposedly, a term meaning, literally "ten thousand years", with an implied "may you live" stuck in there somewhere. I can't find any corroboration for this in either of my Japanese dictionaries, so it may just be some gaijin fairy tale.

Edit:
Oh, d'oh! Banzai. Yup. Ban, ten thousand. Zai (or sai all by itself), years. My one dictionary translates it as Hurrah!