The sorting hat originally belonged to Godric Gryffindor, one of the founders of Hogwarts, and is usually stored in the Headmasters Office. The hat sorts the students into their houses, Gryffindor, Hufflepuff, Ravenclaw and Slytherin, depending on their respective characteristics. The sorting hat sings a song before the sorting takes place ( which Ron Weasley thought it takes the whole year to make up). During the opening banquet at the beginning of each year the students line up, and have their names read out. As their names are read out, each student sits on a stool and the hat is placed on their head. After a short moment the hat annouces their house, and the students joins the house's table. The hat sometimes speaks to the student while it is deciding on the sorting, especially with hatstalls.
Hatstalls occur when the sorting hat is divided between two houses, as the student in question is suited to both. The hat will often take the student's opinion into account if this is the case, such as when Harry Potter could have been sorted into Slytherin, but chose Gryffindor instead. Other notable hatstalls include Hermione Granger (a Gryffindor who could have been a Ravenclaw), Neville Longbottom (a Gryffindor who could have been a Hufflepuff), Minerva McGonagall (a Gryffindor who could have been a Ravenclaw) and Filius Flitwick (a Ravenclaw who could have been a Gryffindor).
The sorting hat was not only seen to be sorting students, as it was also found in the Chamber of Secrets, where it provided Harry with Godric Gryffindor's sword in order to kill the Basilisk. The hat is later seen with Neville, who takes the Sword of Gryffindor from it to kill Nagini, and Voldemort attempts to destroy the hat. However, it is known to be used in later years.
The hat's songs as stated in the books:
 Philosopher's Stone
Oh, you may not think I'm pretty,
But don't judge on what you see,
I'll eat myself if you can find
A smarter hat than me.
You can keep your bowlers black,
Your top hats sleek and tall,
For I'm the Hogwarts Sorting Hat
And I can top them all.
There's nothing hidden in your head
The Sorting Hat can't see,
So try me on and I will tell you
Where you ought to be.
You might belong in Gryffindor,
Where dwell the brave at heart,
Their daring, nerve and chivalry
Set Gryffindors apart;
You might belong in Hufflepuff,
Where they are just and loyal,
Those patient Hufflepuffs are true
And unafraid of toil;
Or yet in wise old Ravenclaw,
If you've a steady mind,
Where those of wit and learning,
Will always find their kind;
Or perhaps in Slytherin
You'll make your real friends,
Those cunning folk use any means
To achieve their ends.
So put me on! Don't be afraid!
And don't get in a flap!
You're in safe hands (though I have none)
For I'm a Thinking Cap!
 Chamber of Secrets
Harry missed the sorting on his second year, as he and Ron flew the Weasleys' car to Hogwarts after Dobby had sealed the gateway to Platform 9 3/4, and crashed it into the Whomping Willow that sits on the school grounds.
 Prisoner of Azkaban
Harry also missed the sorting his third year because a dementor had crawled into the trio's compartment on the Hogwarts Express, and the very presence of the Dementor made Harry pass out. Harry was taken to Professor McGonagall's office when the train reached Hogwarts.
 Goblet of Fire
A thousand years or more ago,
When I was newly sewn,
There lived four wizards of renown,
Whose names are still well known:
Bold Gryffindor, from wild moor,
Fair Ravenclaw, from glen,
Sweet Hufflepuff, from valley broad,
Shrewd Slytherin, from fen.
They shared a wish, a hope, a dream,
They hatched a daring plan
To educate young sorcerers
Thus Hogwarts School began.
Now each of these four founders
Formed their own house, for each
Did value different virtues
In the ones they had to teach.
By Gryffindor, the bravest were
Prized far beyond the rest;
For Ravenclaw, the cleverest
Would always be the best;
For Hufflepuff, hard workers were
Most worthy of admission;
And power-hungry Slytherin
Loved those of great ambition.
While still alive they did divide
Their favourites from the throng,
Yet how to pick the worthy ones
When they were dead and gone?
'Twas Gryffindor who found the way,
He whipped me off his head
The founders put some brains in me
So I could choose instead!
Now slip me snug about your ears,
I've never yet been wrong,
I'll have a look inside your mind
And tell where you belong!
 Order of the Phoenix
In times of old when I was new
And Hogwarts barely started
The Founders of our noble school
Thought never to be parted:
nited by a common goal,
They had the selfsame yearning
To make the world's best magic school
And pass along their learning.
"Together we will build and teach!"
The Four good friends decided
And never did they dream that they
Might someday be divided,
For were there such friends anywhere
As Slytherin and Gryffindor?
Unless it was the second pair
Of Hufflepuff and Ravenclaw?
So how could it have gone so wrong?
How could such friendships fail?
Why, I was there and so can tell
The whole sad, sorry tale.
Said Slytherin, "We'll teach just those
Whose ancestry is purest."
Said Ravenclaw, "We'll teach those whose
Intelligence is surest."
Said Gryffindor, "We'll teach all those
With brave deeds to their name,"
Said Hufflepuff, "I'll teach the lot,
And treat them just the same."
These differences caused little strife
When first they came to light,
For each of the four founders had
A House in which they might
Take only those they wanted, so,
For instance, Slytherin
Took only pure-blood wizards
Of great cunning, just like him,
And only those of sharpest mind
Were taught by Ravenclaw
While the bravest and the boldest
Went to daring Gryffindor,
Good Hufflepuff, she took the rest,
And taught them all she knew,
Thus the Houses and their founders
Retained friendships firm and true.
So Hogwarts worked in harmony
For several happy years,
But the discord crept among us
Feeding on our faults and fears.
The Houses that, like pillars four,
Had once held up our school,
Now turned upon each other and,
Divided, sought to rule.
And for a while it seemed the school
Must meet an early end,
What with dueling and with fighting
And the clash of friend on friend
And at last there came a morning
When old Slytherin departed
And though the fighting then died out
He left us quite downhearted.
And never since the founders four
Were whittled down to three
Have the Houses been united
And they once were meant to be.
And now the Sorting Hat is here
And you all know the score:
I sort you into Houses
Because that is what I'm for,
But this year I'll go further,
Listen closely to my song:
Though condemned I am to split you
Still I worry that it's wrong,
Though I must fulfill my duty
And must quarter every year
Still I wonder whether sorting
May not bring the end I fear.
Oh, know the perils, read the signs,
The warning history shows,
For our Hogwarts is in danger
From external, deadly foes
And we must unite inside her
Or we'll crumble from within
I have told you, I have warned you..
Let the sorting now begin
 Half-Blood Prince
After Harry's meeting with the "Slug Club" on the train towards Hogwarts, Harry decided to follow Blaise Zabini as he entered into a Slytherin compartment containing Draco Malfoy. However, when done 'spying' on him, Malfoy cast the body-binding spell and Harry couldn't move a muscle, especially after Malfoy broke his nose, and therefore Harry missed the Sorting Ceremony.
Related Threadsthe sorting hat plus keeper of house points - last post by @ Dec 2, 2001
Sorting Hat - last post by @ May 29, 2009