Objective-C was created in the early 1980s by Brad Cox as a set of minimal extensions to C to support Smalltalk-style objects easily. It grew out of the Object Oriented Pre-Compiler (OOPC) project, which had very similar semantics to those of Objective-C but some really horrible syntax.
The initial implementation and the Objective-C trademark were bought by NeXT, which used it all over its new operating system. NeXT built a GUI toolkit in Objective-C and an interface builder. This is widely considered to be the first commercial rapid application development (RAD) tool. It also had the nice side-effect that the interface builder didn't just store an interface description—it stored serialized objects. This approach allowed a clean model-view-controller separation to be maintained while storing the controller and view in a loadable format.
In the early 1990s, NeXT and Sun partnered to build a portable version of the NeXT environment. While NeXT's initial system used pure C in a lot of places, the new version defined two frameworks: Foundation and AppKit. Foundation defined core functionality, including collection classes, strings, and a variety of other things. AppKit contained the GUI frameworks. The two were defined in the OpenStep specification, which was implemented by NeXT, Sun, and later by the GNU Project. After buying NeXT, Apple renamed its OpenStep implementation "Cocoa." Since OpenStep was based on earlier NeXT designs, all of the classes in OpenStep are prefixed with NS.
The story of GCC's support for Objective-C is somewhat interesting. The initial implementation was written by NeXT, but kept in a separate library that users would link with their version of GCC. By not distributing it with GCC, NeXT hoped to circumvent the GPL. This trick didn't work, and NeXT was eventually required to release the code. However, releasing the source code for the runtime library wasn't required, which meant that the compiler wasn't useful on any other platforms. Richard Stallman wrote a new version that was a drop-in replacement for the NeXT runtime. This was later replaced by newer versions that diverged in various ways.
The current code for Objective-C in GCC depends on the branch you use. NeXT kept its own version, which has a barely-maintainable mess with no layering and everything in a single source file, and only supports the NeXT runtime. Mainline GCC includes a completely unmaintainable mess, based on the NeXT code but littered with #ifdefs for the GNU runtime.
Once Objective-C was supported by GCC, attempts to replicate the NeXT environment started. The GNUstep project eventually evolved from these, and implements pretty much all of OpenStep and a number of Cocoa additions. It also includes a replacement for NeXT's Interface Builder: the GNU Object Relational Modeler (GORM).