Thumbnails are cached on Android, so they don't have to be created on the fly every time you look at the images.
As for generating them on the fly, the gallery can definitely do it. At the very least it does show me thumbnails of the images that didn't have any embedded thumbnails.
Embedded thumbnails do exist, but I have no clue whether the gallery takes advantage of them.