Perhaps the most radical departure from the book is the timeline; the book starts in the summer of 1995 (as established in Chamber of Secrets), but when Harry carries Dudley home a 2006 numberplate is clearly visible in the background, and shortly afterward when Harry travels to London we see the London Eye (not erected until late 1999). Clearly the makers of the movie wanted to set it closer to our time, and J K Rowling didn't object to this.
As with many of the movies, there is a longer sequence in the book at the Dursleys, who receive multiple owl messages the night of the dementor attack. When the Dursleys want to expel Harry from their house, one of the magic letters, in an unknown booming voice, reminds Aunt Petulia of a 'promise' she once made; she reluctantly convinces Vernon to let Harry stay. She gives no explanation, but she obviously knows more about wizarding than she has previously let on.
Harry's overall attitude has been strongly toned down in the movie. In the book, he bursts into several fits of rage directed at his friends when he feels frustrated, grieved or misunderstood. The darker sides of Harry's character and the implied similarities he shares with Voldemort are less overt in the movies than they are in the books.
Much more time is spent at Grimmauld Place. The character of Mundungus Fletcher, a shady small-time criminal member of the Order of the Phoenix, is introduced (perhaps he is one of the silent Order members accompanying Harry to Grimmauld Place in the movie, but he is otherwise absent from the film). There is constant turmoil coming from the painting of Sirius' late mother Walburga, who was a silent supporter of Voldemort, and therefore firmly opposed to the presence of the Order in her house. Kreacher is still very loyal to her, and executes Sirius' orders with the utmost reluctance (while constantly muttering vile curses under his breath). In Harry's room at Grimmauld Place, there is a painting of Phineas Nigellus Black (the least popular Headmaster of Hogwarts, according to Sirius), who also has a painting in Dumbledore's office at Hogwarts, so that his image can travel back and forth between the places. There is a memorable scene where Mrs. Weasley encounters a boggart, which shows her greatest fears to be her family and Harry dying horrible deaths. Ron and Hermione are notified that they will be prefects for the new school year, but Harry won't. Also at Grimmauld Place, the students help Mrs. Weasley with cleaning to prepare it as the headquarters of the Order of the Phoenix. One of the items found during the cleaning is a locket that may play further along in the series. The scene in which Harry receives a two-way mirror from his godfather was omitted from the film, which could cause a significant problem in later films in the series.
Harry notices the Thestrals pulling the chariots right when he arrives back at Hogwarts, but the explanation about why he and Luna can see them and the rest can't is given much later, by Hagrid (not Luna) during a class about the animals (see below). In the book, Neville can see the Thestrals as well, because he saw his grandfather die (the movie does not suggest that Neville can see them).
There is a sequence, completely omitted from the movie, set at St. Mungo's Hospital where Harry and the Weasleys go to visit the injured Mr. Weasley. They accidentally encounter Gilderoy Lockhart, who is still recovering from his self inflicted memory charm from Harry Potter and the Chamber of Secrets. While in his ward, they encounter Neville Longbottom and his grandmother, who are visiting Neville's parents.
Dumbledore appoints Firenze, a Centaur first seen in Harry Potter and the Sorcerer's Stone, as Professor Trelawney's replacement for Divination. This angers the rest of the Centaurs and explains their aggressive behavior towards Harry, Hermione and Umbridge later.
While at Hogwarts, Harry keeps in close contact with Sirius through owl messages and secret Floo Network calls (Sirius is nearly caught by Umbridge at one such instant, causing her to start monitoring the Network). Sirius, being still a fugitive, needs to stay in Grimmauld Place at all times, causing him to become edgy and irritated, and he frequently clashes with Severus Snape, whose role in the Order becomes ever more prominent. Harry hears about Dumbledore's wish to learn Occlumency from Snape during a holiday spent at Grimmauld Place. Upon hearing this, Sirius threatens Snape with serious consequences (almost to the point of duelling), should Snape abuse these lessons to harass Harry.
When inquiring about a suitable place to train with Dumbledore's Army, Harry learns about the Room of Requirement from Dobby the House Elf. Dobby is also the one to warn the army when Umbridge raids the place.
The book has the Inquisitorial Squad in a much more prominent position. There are numerous instances of Draco Malfoy and other members abusing their powers to scare, bully and remove House Cup points from various students. A long plot-line in the book, completely omitted in the film, concerns Quidditch. Harry's detentions get in the way of practice, Ron joins the team as Keeper, and the team is nearly disbanded after an Educational Decree. Draco taunts Harry at one instant, causing Harry to punch Draco. Professor Umbridge reponds to this by banning Harry from playing Quidditch for life. Ginny joins as Seeker after Harry's been banned, but Ron's uncertainty about his Quidditch talents gives the team little chance to win. This is worsened by the Slytherins, who keep taunting Ron with their chants during the matches.
The way in which Harry gets access to Snape's worst memory is different. In the movie he reverses one of Snape's Legilimency spells; in the book, Snape empties his memories in Dumbledore's Pensieve every time before the Occlumency lesson, in order to prevent Harry from inadvertantly seeing them. At one such lesson, Snape is called away by Draco and the Inquisitorial Squad, and Harry uses this moment to look into the Pensieve. The flashback is more detailed. Sirius Black, Remus Lupin, and Peter Pettigrew were present (one boy to the left of James resembles Sirius), and Harry's mother intervenes to stop them. However, a bitter Snape insults Lily for being friends with James. At that point, Harry is pulled out of the Pensieve by Snape, who furiously dismisses him.
While Hagrid's return is in the film, his return to teaching is not. He tries to hold a class about Thestrals while being much interrupted and disturbed by Dolores Umbridge. Before that, he introduces Harry and Hermione to Grawp, who is much more aggressive and less good-natured than portrayed in the movie. In the book, Ron does not meet Grawp when Harry and Hermione do. He is off playing in the Quidditch final, in which Griffindor unexpectedly wins, and Harry and Hermione tell him about Grawp much later.
Hagrid is later fired, and even faces arrest by the Ministery. Because of an intervention by Professor McGonagall, he escapes. However, McGonagall is severely injured by stunning spells during this altercation.
There is much more about the O.W.L.s and how the students do on them. The students are told they have to choose a career path in order to determine which classes they need to take. Harry decides he'd like to be an Auror. During one of his O.W.L.s he gets to perform a Patronus for an extra point.
Most of the awkward romance between Harry and Cho has been omitted, including a disastrous Valentine's coffee-shop visit. In an attempt to get the truth about Voldemort out, Harry gives an exclusive interview to Rita Skeeter, telling details of Cedric Diggory's death. (In Goblet of Fire, Skeeter had been blackmailed into silence by Hermione, who discovered she was an unregistered animagus.) The interview is published by Luna Lovegood's father in his magazine, The Quibbler.
In the scene where Fred and George leave Hogwarts before they leave, they tell Peeves (a nasty troublemaker of a poltergeist) to "Give her hell from us!", referring to Umbridge. There is also more in the book about Peeves, amongst other things, for the first time ever working together with the students. Also, McGonagall seems to favor Peeves' mischief: as she walks by Peeves, who is trying to unscrew a chandelier, she mutters, "It unscrews the other way."
There are two separate instances of disruptions made by the Weasley twins, to help Harry use Umbridge's fireplace for communication with the Order. In the first instance they use their own brand of fireworks and in the second one, before they are caught, they conjure a swamp in one of the corridors. They publicly take credit for the swamp, to the point of advertising their Portable Swamp, and leave the school and are thus never actually expelled.
In the book, Harry gets his vision of Sirius being tortured by Voldemort in the middle of an O.W.L. and not after Fred and George's final stunt. He faints and is dragged away. His friends try to convince him that it may be a fake vision by Voldemort, but he does not want to hear of it. They set up another diversion in order to lure Umbridge away, so they can use the fireplace in her office. Harry manages to make a 'call' to Grimmaulds Place, where Kreacher tells him Sirius has indeed left the house, but he is abruptly interrupted by Umbridge and the Inquisitorial Squad. Dolores Umbridge herself reveals to be the one who sent the Dementors after Harry and Dudley (see FAQ below). In the book, Dumbledore's Army is not betrayed by Cho Chang (who was coerced with Veritaserum), but by another girl named Marietta who suffers a horrible case of acne because of a hex Hermione had placed on the sign-up sheet. Note that the other girl was invited by Cho to the army's meetings, so Cho felt guilt in any event.
It is later revealed that The Order of the Phoenix was betrayed by Kreacher, Sirius Black's house elf, when Sirius, in a fit of anger, gives Kreacher an order that permits him to speak to Sirius' cousin, Bellatrix Lestrange. Kreacher had lied to Harry on purpose by saying Sirius had left the house, in order to lure Harry to the Ministry.
The sequence in the Department of Mysteries is much longer. The members of Dumbledore's Army and Death Eaters battle and hex each other all through the different rooms of the Department. While the two groups are fighting in the Death Chamber, it was Neville, not Lucius, who drops the prophecy by accident. Sirius Black is not killed by the killing curse in the book. It does not define which curse is used, except to say that there were red lights/sparks. The killing curse is known for having a green light. The assumption is that Avada Kadavera was used in the movie for people who do not read the book, thus saying with certainty that Sirius Black is dead. The book describes Sirius being stunned and then falling over, but he tragically tumbles through the arch, which seems to be a one-way passage to death.
When Harry, Bellatrix and Voldemort are in the lobby of the Department of Mysteries, Voldemort learns that the prophecy he has been after for so long has been smashed and attempts to kill Harry using the Avada Kedavra. Before the spell can reach him, Dumbledore summons the golden statues in the lobby's fountain to protect Harry.
Harry's attempted possession by Voldemort is made much more dramatic in the film, whereas in the book Harry isn't sure what's happening to him and is informed after the fact by Dumbledore what Voldemort was attempting to do. None of the dialogue of Voldemort speaking through Harry or Harry rejecting Voldemort is in the book.
Harry is also much more upset after Sirius' death, to the point of angrily breaking objects in Dumbledore's office. It should be noted, though, that in the book, the scene in the office follows almost directly after the fight at the Ministry, when Harry's rage and grief are still fresh. In the movie, there seem to be several days in between, so Harry had some time to cool off and come to terms with Sirius' death.
The explanation Dumbledore gives to Harry about all events of the past year is much more elaborate. It turns out that the prophecy stored at the Ministry spoke about a boy who was soon to be born from a wizard family, meaning it could have applied to either Neville Longbottom or Harry Potter. Dumbledore believes Voldemort saw Harry as the one to whom the prophecy specifically referred, because they are both half-blood, and he therefore felt some sort of connecting bond. When it came to the prophecy, no one heard it at the Department of Mysteries. Harry had to find out from Dumbledore what the prophecy says, and then tells Ron and Hermione. Ginny, Luna, and Neville know nothing of what the prophecy is about. Also, it is explained that Dumbledore knows about what was said in the prophecy because he heard it predicted years ago by Professor Trelawny, who came to apply for the job of Divination Professor. This is why she got offered her job. It is also explained that a Death Eater overheard the beginning of the prophecy, but missed the crucial part about the Dark Lord 'marking his nemesis as his equal,' which is why Voldemort attacks Harry and his parents (and by trying to prevent the prophecy from happening, he created his nemesis and inadvertently fulfilled the prophecy himself). It is possible that only Harry heard the prophecy because he was holding it.
Dumbledore also explains the reason why Harry was left with his condescending aunt and uncle, and why he was sent back there every summer. When Harry's mother was killed trying to save Harry, her sacrifice out of love created a magic protection for him (the 'old magic' Voldemort referred to in Harry Potter and the Goblet of Fire). The proximity of her blood protects Harry from harm until he comes of age. As Aunt Petunia, being Lily's sister, carries the same blood, the protection also works in her presence, as long as Harry is underage. So the place Harry always detested most is, ironically, the safest place for him to be. Dumbledore explained this to Petunia in the letter he left on baby Harry, and made her promise to keep him there for his protection. The booming voice coming from the letter in the beginning, reminding Petunia of her promise, was Dumbledore's.
Dumbledore also subtly implies that Sirius may have warranted Kreacher's betrayal, and thereby his own death, by treating Kreacher so badly, which enrages Harry even further. Furthermore, Dumbledore rescues Umbridge from the Centaurs after he returns to Hogwarts, though we never see how. Harry has a conversation with Nearly Headless Nick, broaching the possibility of Sirius returning as a ghost. Nick explains that he and most other ghosts chose their fate because they were afraid of leaving this world. Harry takes a peek in his two-way mirror, hoping for a sign of Sirius from beyond, but it remains empty.
After Lucius Malfoy and most of the other Death Eaters are captured, Draco, Crabbe, and Goyle confront Harry at Hogwarts and give him death threats. Harry tells them that after confronting Voldemort and the Death Eaters, he's not afraid of anything they might try. At King's Cross Station, Professor Moody warns the Dursleys to give Harry a proper treatment this time, or he will intervene.