Here's what I did:
Opening Song: My Hands Say Hello - This is our standard opener and signals to the kids that it's time to start storytime. In this song, they practice saying hello to their new friend (me!). It also gives them a chance to move their hands, feet, and other body parts to get out some wiggles so they're ready to sit and listen.
Mail: I love to start an All About Me storytime with some mail to the kids. I reused a manilla envelope and printed a simple letter to the kids welcoming them to the library and explaining that we were going to share stories and songs all about me. Before I got the letter out, I went through each line of the address with them. This reinforces the concept that print is used in lots of different ways. And we talked about the name of our street, the name of our town, and the name of our state. I got this idea from Storytime Katie, who saw it in a post from Amanda Struckmeyer on Wisconsin's Youth Services Shout-Out collaborative blog).
Felt Story: Mr. Pine's Purple House by Leonard Kessler. This story of a man who tries to make his house distinctive from his neighbors is a great introduction to talking about our own houses. It's also a great story for emphasizing the concepts of same and different. After Mr. Pine makes a change to his house, I ask the kids if his house is the same or different. I ask again after all the neighbors have followed suit and the houses look alike again.
Book: I Can Do It, Too! by Karen Baicker, illustrated by Ken Wilson-Max. This book uses simple, rhyming text to introduce many things that young children can do - get dressed, help bake a cake, read books with their grandparents, etc. As I read this book, I asked the kids if they did some of the things in this book, too.
Song: Head, Shoulders, Knees, and Toes. The kids were pretty squirrelly at this point, so we needed to get up and move a little bit. This is a familiar song and the kids were proud that they knew it and they could do the motions along with me. It also helped introduce body parts, which tied into our next story.
Book: We've All Got Belly Buttons by David Martin, illustrated by Randy Cecil. This brightly illustrated book shows different animal body parts (ears, neck, hands, etc.) and encourages children to move along as you read it. The interaction helps keep the kids' attention and the text reinforces the vocabulary for different body parts.
Book: The Family Book by Todd Parr. Learning about each other's families is definitely something you do when you meet new friends. I love Todd Parr's book for this because it has silly, colorful illustrations and it's very inclusive. Without making a huge deal, the book lets kids know that some families are the same color and some families are different colors, some families have two moms or two dads and some families have just one parent. The text always comes back to something all families have in common, for instance all families help each other be strong.
Felt Activity: Color Library Cards. Since it's National Library Card Sign-Up Month and since this was a group coming into the library, I brought out these felt library cards for a fun ending activity. I passed out the pieces and as I called each color, children came and put their card up on the board. This activity not only reinforces color concepts, it helps kids practice following directions and interacting with an adult who is not in their family (or their teacher, in this case).
Closing Song: Do You Know What Time It Is? - This is our standard closing song and a signal to the kids that storytime is over and it's time for them to pay attention to teacher and find out what to do next.
Alternate Ideas: If you don't like or don't have any of the books I used, here are some sources for more ideas: