The scene where the alien that Kay killed in the beginning of the film transformed was not originally planned. The creators added it in because they realized that most people would have sympathized with the alien had he died as is, and wanted to ensure no sympathy was to be gained for the alien prior to being killed.
Will Smith's line "It just be rainin' black people in New York!" was improvised but so hilarious that they decided to leave it in.
As was his line in the sequel when showing Kay the car: "It used to come with a black man, but it kept getting pulled over". Apparently they reused it so much that he soon became sick of it.
In fact, most of the lines in the final product were this. Tommy Lee Jones didn't like the script and made up most of his dialogue on the spot, with Will Smith trying to keep up. It was hilarious enough that Barry Sonnenfeld just didn't care and threw it ALL in. And the movie ended up being praised for its witty dialogue, in case you needed more proof how awesome Tommy Lee Jones is.
In MIB II, rapper Biz Markie was visiting Will Smith on the set and they were beatboxing to each other. Sonnenfeld saw this, loved it, put Markie in as an alien in the post office scene, and added the part where J speaks to him in his native language (which was really just their beatbox routine).
According to the book The Man Behind the Mask, Michael Jackson would have appeared in the sequel for free...if Will Smith were dropped from the film so he could be the protagonist. He couldn't convince Sony's higher-ups that this was a good idea, hence the cameo instead.
Bruce Campbell was the one originally in mind to play the exterminator, but he turned it down to appear in some TV movie that even some of his more hardcore fans haven't heard of.
Clint Eastwood was originally offered the part of Kay, but declined.
Among the options for the role of Jay was David Schwimmer of Friends fame. Imagine a Men in Black starring Clint Eastwood and David Schwimmer.
The sequel would've used the World Trade Center in some way, but then 9/11 happened.
Originally, there were going to be two alien ships looming over the Earth, demanding the return of the galaxy: the Arquillian ship, and a Baltian ship (Rosenberg was originally a Baltian in the script). The initial volley is compared to two gunslingers using a giant rock as cover. Some work was done in post production (dubbing the aliens' conversation into "alienspeak", for one), and long story short, Rosenberg became an Arquillian.
