What is the difference between a mod and a plugin

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.

This is confusion of type and subtype:

A "mod" is any change to the basic system, however that's accomplished. Just short for "modification". If it's different, you modified it.

A "plugin is simply a modular change that the developers planned to accommodate without needing to change the existing files. That is, it calls the changes in the plug-in when appropriate and can be removed without changing the system files themselves.

All you need to do to revert the behavior is to remove the plugin.

A "patch" is a direct change to (at least one of, though possibly multiple of) the basic system files. This is what plugins allow you to avoid. To undo these, you need the original data files or run the patching backwards; the latter is normally quite difficult.

There are also real-time mods like trainers which simply alter memory as it's being loaded or after, but that's beyond the scope of my answer.

(Valve labeling a patch a mod is perfectly legitimate since it's both.)

To simplify*:

A computer game is made up of various files. These define the game, from the code that sets the system to the music and graphics.

To alter those files by either replacing them or patching them (patching is altering only part of the data.) allows you to change the game.

A plug-in system allows a third option: Plug-ins let a game load changes from somewhere else without altering the game files at all.

The changes allowed have to be planned* in to be possible. If the programmers didn't think to allow a type of mod through a plug-in, you simply can't* do it.

Any of those changes is a modification of the game: a "mod".

(*generally true)