What is the difference between a mod and a plugin
Solution 1:
As you mentioned Minecraft as a prime example of game regarding your question, here is a Minecraft related answer:
Wrapper: Sits between the Java runtime and Minecraft server -- usually provides extra functionality externally (i.e. providing remote management, querying, statistics, and uptime assurance) and work by simply inputting commands to the Minecraft server console and listening to what they return (stdio). They usually do not need updating when Minecraft is updated as they are not dependant Minecraft in any way, but are more limited in what functionality they can provide in game. Multiplay Admin and McAdmin are wrappers.
Mod: Decompiled Minecraft server binary and injected with modified code -- usually internally (i.e. providing extra commands, game play changes, and a plug-in framework). As they have to modify the game code they will almost certainly need updating when Minecraft is updated to be compatible with the core updates, but can offer a much wider range of in game functionality than a wrapper. hMod, CraftBukkit, and Llamacraft are mods.
Plug-in: Dynamically loadable code that sits on top of a plug-in framework to create an unmatched level of extra features with ease. They often don't need updating when Minecraft is updated as they depend on the framework from the mod, and any required update is often trivial work. iConomy, Stargates, WorldEdit, and WorldGuard are plug-ins.
To add and expand to this: In counter strike 1.6 you'd have mods like TFW3 or jail break or zombie mod. AND THEN you can add plugins to these mods, like the long-jump plugin to the zombie, the 2nd items shop to the War3 mod, or the jet-pack etc.
Solution 2:
This is a bit of a tricky one, because the terms are used interchangeably in the gaming world, and have changed in meaning over the lifetime of gaming.
As you said, they both modify gameplay, but I think the difference between them comes in how they are made and run, and their size/scope:
Plug-ins, as suggested by their name, are things which are plugged in to other bits of software, using an API that the developers of software provide. A (non-gaming) example of this would be the apps available to install in the Chrome browser. The developers of Chrome provide an API for the development of the apps, and anyone can freely create one. Plugins are typically quite small and only modify a limited amount of things.
Mods then typically refer to modifications made for a piece of software without the original developer's permission, and often signify quite an invasive method of changing the gameplay. For example: changing or replacing .dlls or .exes to modifiy or replace source code; or editing 3D models and/or textures. Mods are typically quite big and aim to do a lot of things.
The big problem that muddies the water with these two terms is the fact that now, more and more developers are supporting modification of their game, and typically label it as "This game now supports modding!", when in fact, since they are providing an API, it should probably really be "This game now supports plug-ins!". However, if you said that to the average consumer, they would probably look at you slightly confused. Everyone is much more content with modding, as it has that cooler conotation of hackers, green terminal text and your super-nerd friend who speaks Assembly and can reverse-engineer C++ in 10 minutes.
So to use Minecraft as an example, I would say it only has mods, such as Forge and Bukkit, which are not officially supported by the developers, but then those mods themselves have plugins, as the mods actually provide the APIs that the plugins use, not Minecraft itself.