Jar Jar's introduction was originally a little more elaborate than we saw in the movie. In the film, he just sort of appears in all the confusion, grabbing on to Qui-Gon as he passes by him. According to the Illustrated Screenplay, however, Jar Jar is enjoying a nice morning meal before the ruckuss. This is further supported by his small speech to Padmé later on aboard the Queen's ship when he tells her about how the day "...starten out pitty okeyday witda brisky morning munchen."

An odd, frog-like creature Gungan, JAR JAR BINKS, squats holding a clam he has retrieved from the murky swamp. The shell pops open. Jar Jar's great tongue snaps out and grabs the clam, swallowing it in one gulp.

Jar Jar is a friendly Gungan, as we all know but did you know that he was originally supposed to hug and kiss Qui-Gon after he saved Jar Jar from getting run over in the swamp?

There originally was a scene in the swamp where we see Obi-Wan hiding in a Naboo lake. He has just left the Federation ship he stowed away on and is getting ready to meet up with Qui-Gon. His head comes up and in the background you can see the Federation Troops readying for the big invasion. Obi-Wan takes a few deep breaths and submerges into the muddy water once again.

Exterior:
Naboo Swamp - Twilight
 
In the distance, two STAPS burst out of the mist at high speed, chasing OBI-WAN.
QUI-GON: I have no time for this now...
JAR JAR: Say what?
The two STAPS barrel down on OBI-WAN.
JAR JAR: (cont'd) Oh, nooooo! Weesa ganna....
QUI-GON throws JAR JAR into the mud.
QUI-GON: Stay down! His head pops up.
JAR JAR: ...dieeee!
The two troops fire laser bolts at OBI-WAN. QUI-GON deflects the bolts back, and the STAPS blow up. One-two.

After Qui-Gon uses his lightsaber to save Obi-Wan from the STAPs, Qui-Gon scolds Obi-Wan slightly, reinforcing the Master/Apprentice relationship they have together. Here's the scene as it reads in the Illustrated Screenplay. In the film, this takes place right before Jar Jar pops up and Obi-Wan asks, "What's this?" Read on:
OBI-WAN is exhausted and tries to catch his breath.
OBI-WAN: Sorry, Master, the water fried my weapon.
OBI-WAN pulls out his burnt laser sword handle. QUI-GON inspects it, as JAR JAR pulls himself out of the mud.
QUI-GON: You forgot to turn your power off again, didn't you?
OBI-WAN nods sheepishly.
QUI-GON: (cont'd) It won't take long to recharge, but this is a lesson I hope you've learned, my young Padawan.
OBI-WAN: Yes, Master.
JAR JAR: Yousa sav-ed my again, hey?
OBI-WAN: What's this?
QUI-GON: A local. Let's go, before more of those droids show up.
JAR JAR: Mure? Mure did you spake??!?
OBI-WAN and QUI-GON start to run. JAR JAR tries to keep up.
JAR JAR: (cont'd) Ex-squeeze me, but da moto grande safe place would be Otoh Gunga. Tis where I grew up...Tis safe city.
They all stop.
QUI-GON: A city! (JAR JAR nods his head) Can you take us there?
JAR JAR: Ahhh, will...on second taut...no, not willy.
QUI-GON: No??!
JAR JAR: Iss embarrissing, boot... My afrai my've bean banished. My forgoten der Bosses would do terrible tings to my. Terrible tings if my goen back dare.
A PULSATING SOUND is heard in the distance.
QUI-GON: You hear that?
JAR JAR shakes his head yes.
QUI-GON: (cont'd) That's the sound of a thousand terrible things heading this way...
OBI-WAN: When they find us, they will crush us, grind us into little pieces, then blast us into oblivion!
JAR JAR: Oh! Yousa point is well seen. Dis way! Hurry!
JAR JAR turns and runs into the swamp.
Here's something interesting. In the film we see the Neimoidians coming out their ship in the main square of Theed Plaza. They are on their way to the Palace and OOM-9 informs them that he has captured the Queen. We never get to see this ship of theirs completely. We can just see a leg and some of the base as they come out. in this shot from the Comic Adaptation, we get to see the whole ship and it looks pretty nice. it would have been great to see it landing in the plaza.
 

Sabé, the Queen's handmaiden, was originally not the only decoy in Episode One. The Queen's ship, according to the Episode 1 Insider's guide CD-ROM, was also used as a decoy. Check out this passage:

In the revised third draft, the Queen's starship actually lands directly in one of the Royal Palace's courtyards. It is surrounded by battle droids and a tank. However, when droids led by a droid commando named 044 search the starship, they find nothing. Evidently, the Queen and her entourage abandoned the starship near Otoh Gunga, then programmed the autopilot to fly to the Royal Palace. Later, Nute reveals that the Trade Federation forces have located the "life pods" used by the Queen and her followers.

This is interesting stuff. Perhaps some of you might remember a rumor long before the film was released which I'll dub the "Marie Celeste" rumor. According to some sources on various websites, the Queen's Nubian chrome ship was to be called the Marie Celeste. Someone had actually researched this and found out that the Marie Celeste (or Mary Celeste) was actually an old vessel whose crew had mysteriously disappeared in 1872 without a trace, leaving no indication as to why they left the ship.

We know that in the film the ship is never referred to by name, just make and model. There is evidence, however, in the shooting script that the ship was at one point referred to as the Marie Celeste. The scene described above is also in the shooting script and not only is Nute present in the scene but Darth Maul as well. It is listed as:
  According to the Illustrated screenplay, there was a short scene where Jar Jar swims back down to Otoh Gunga in search of the Gungans after the trip back home from Coruscant. In the film we only see him returning and coming out of the water to report that the city is deserted, but in the original drafts he actually swam down and looked around. Here's the excerpt from the Illustrated screenplay:


EXT. NABOO SWAMP - UNDERWATER - DAY (FX)
JAR JAR swims down into Bubble City.

INT. OTOH GUNGA - CITY SQUARE
JAR JAR enters the main square of the bubble city. He stands, stunned, in amazement and fear. He is nervous and shaking.

Jar Jar
Ello! Where das everybody?

The plaza is empty. He notices that many of the buildings are shot up as if there had been a battle of some kind.
Sometime during the conception of Amidala's plan to capture the Viceroy, Nute Gunray, this shot falls into place. Here is a great shot of Ric Olié in the greens of Naboo, awaiting his orders. It's from the Episode 1 Insider's guide.
 

There was originally another scene to take place in the Naboo Palace Throne room after the capture of Nute Gunray. Many Battle Droids are firing at the closed Throne Room door trying to get inside. This scene is still intact in the novelization, as seen here:

Blaster shots hammered into the door of the throne room in the palace at Theed. Captain Panaka and the Naboo soldiers spread out to either side in a defensive stance, preparing a crossfire for the droids. Nute Gunray wanted to move out of range, but the Queen was still facing him, her blaster leveled at his midsection, and he did not care to risk provoking her into a hasty action. So he stood there with the others of the Trade Council, frozen in place.
Then abruptly, everything went still. All sound of weapons fire and droid movement beyond the battered throne room doors ceased.
Captain Panaka looked at the Queen, his dark face uncertain. "What's going on?" he asked worriedly.
Amidala, her weapon pointed at Nute Gunray, shook her head. "Try communications. Activate the viewscreens."
Her head of security moved quickly to do so. All eyes were on him as he slowly brought the outer screens into focus.

As you can see here, Panaka brings up the viewscreens and then we cut over to the plains where the battle is taking place. The strange thing is we never cut back to the throne room to see what happens! We go from the above scene, to the grassy plains and Jar Jar, and then that's it. The book goes from there to three days later where Obi-Wan and Yoda speak of Anakin's training. I do know, however, that there was originally another scene where Ric Olié reports to the Queen and informs her that the battle is over. My guess is that this is the scene right after Panaka brings up the viewscreens. They probably see Ric on the monitor and he talks to them. While I'm not sure of the dialogue from this scene, there is a card from the Decipher CCG "Menace of Maul" set (Bravo One is the card name) that has a quote from Ric Olié on it and he says, "Mission Accomplished, Your Highness." My guess is this is from that scene. I don't think Decipher would make up lines so they must have gotten an earlier draft of the script with many of the cut scenes intact. There are some other quotes on those cards that were not in the film either.