Gems are Ruby libraries; they are the subject of my earlier book,Practical Ruby Gems. Rails itself is packaged as a gem, and so are a variety of other Ruby software packages: fasterCSV is an optimized CSV library packaged as a gem, hpricot is an HTML parser library packaged as a gem, and so forth.
Plugins are specifically designed to extend Rails; they are placed inside a Rails application and are automatically loaded by Rails. Unlike Gems, they are unique to an application: if five of your apps use the Attachment Fu plugin, all five will contain a separate copy.
However, the two types are not completely inseparable: you can, for example, copy a particular gem to your Rails plugin directory; this causes that particular version of the gem to be "frozen," so that your application will always use that version instead of whatever version is most recent.
Additionally, Rails 2.1+ supports packaging plugins as gems; as a result, the essential difference between gems and plugins becomes whether your Rails application is going to load the code from your system or from it's own local copy.