Enforced Method Acting: Tommy Lee Jones was not amused by the script he was given, so he ad-libbed a good deal of his dialogue. Look closely enough and you can see Will Smith trying to keep up, as expected of the fresh recruit. The resulting synergy is well over half the movie's charm.
Science Marches On: A minor one. When J heads to the morgue to retrieve a cat, he hilariously tries to convince Laurel that the cat is a witness in a murder investigation. Fast forward about ten years and advancements in forensic science mean that animals who 'witness' a murder can be checked for any forensic evidence the killer may have left behind.
Technology Marches On: K shows J a small alien disc and says "They're going to replace CDs soon". At this point, it's doubtful. It was based on Sony's MiniDisc, which did indeed fail to be the wave of the future. Also, J's introduction is him chasing down an alien on foot to arrest him. These days, the fleeing suspect probably would have been tazed, ending the chase rather quickly.
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.
In fact, a lot of the lines in the original film were this. Tommy Lee Jones was famously dissatisfied with the script and so he took it upon himself to "fix" it by ad-libbing a good deal of his dialogue and one-liners, The result was Will Smith, not to be outdone, having to play along too. 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.
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). Edgar came to Earth to deliberately start a war between the two races, said to be negotiating peace, so he can feed off the resulting war. The initial volley is compared to two gunslingers using a giant rock as cover. Eventually, they decided the Baltians were not necessary to the plot, so some work was done in post-production (dubbing the aliens' conversation into "alienspeak", for one), and long story short, Rosenberg became an Arquillian.
Know that weird language J speaks in to the guy in the mail room? Well, the mailman is actually Biz Markie, and that "weird alien language" is actually beatboxing.
Let's not forget that Patrick Warburton played a not-too-bright agent who joined MIB because he wants to be a hero. His codename? "Agent T."
A lot of mentions were made of Serleena's ravenous appetite. One scene shows her scarfing down a massive burger. At the time the film was released, Lara Flynn Boyle was in the tabloids a lot because of her emaciated appearance, with a lot of gossips claiming she was starving herself. Like most starlets facing similar accusations, Boyle deflected it by claiming she was actually a Big Eater and just had a superfast metabolism.
Will Smith's 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 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.
The sequel would've used the World Trade Center in some way, but then September 11th happened.
Yeardley Smith, Halle Berry, and Jennifer Lopez originally auditioned for the part of Serleena.
Hinted at. J doesn't like being called a dumbass in some dialogue reminisicent of Hancock.
When J takes a little girl's chocolate milk, she mistakes him for "the president" (Barack Obama). Will Smith has spoken of a desire to portray Obama in a biopic. Obama himself has said that if a biopic is made, Will Smith is his first-choice to star in it.
Griffin's love of baseball. Michael Stuhlbarg's other best-known role, Arnold Rothstein of Boardwalk Empire, has quite a bit to do with the development of baseball in the US.
K is supposed to be 29 in 1969. He's played by Josh Brolin, who was 43 during the filming. J lampshades this, looking incredulously at K and snarking "Got some city miles on ya, huh?"
Inverted with Will Smith as Smith was born in 1968. We learn J was at least 4-5 in 1969, making J a few years older than Will Smith.
Also inverted with O. Emma Thompson was born in 1959 and thus would have been ten in 1969. The younger version of O looks to be in her mid to late twenties and is played by Alice Eve who would have been 28 to 29 during filming.
Fake Brit: In the third film, Boris the Animal is played by the New Zealand actor Jemaine Clement. He's technically an alien, but he speaks with a British accent reminiscent of Tim Curry.
K's voice actor is replaced after the first season. L gets a new voice actress for the final season.
Almost none of the actors from the movie reprised their roles for the show. Tony Shalhoub did reprise Jeebs in a few early episodes, but Billy West did the voice for the remainder of the series.
Suspiciously Similar Song: The theme for the cartoon series carries the first few beats of Will Smith's eponymous "Men In Black" as part of its main theme, but ditches the rest of the song in favor of a instrumental hip-hop composition.