Engine Room
After you complete the main objectives Spin-Dig Galaxy, the Spin Drill appears in the Power-up gallery.
Also, Mailtoad appears on the top of the ship.
The Cloud Flower appears when the main objectives in Fluffy Bluff Galaxy are finished.

Starship Mario
Yoshi is unlocked after the first star in Yoshi Star Galaxy is collected.
After you finish the game the first time, Luigi is unlocked. Follow the stream of water up from the pool on the bottom of Starship Mario (it should look like a green spot with railings around it). Then, walk into the green doors.
The first letter from the Mailtoad includes a 1-Up Mushroom.

World Map
In the World Map, after you feed the Hungry Luma <Edit Later> star bits, he will transform into Flip-Swap Galaxy. After you complete the first star, you can advance. Behind the Galaxy Icon, there is a Star Bit Cluster. Simply run into it to collect it.