I noticed that the yaml module is available in ST3 build 3083 but I have no means to check whether it is supported in older versions.
So my question is: suppose I do import yaml in my plugin, which versions of ST would support it?

It depends where the yaml module came from. There are three possibilities:

1. You have PyYAML installed on your system’s Python and are using SublimeLinter. SL adds the system’s Python’s site-packages dir to ST’s Python’s sys.path in order to import modules like pep8 or flake8.
2. Some package included PyYAML on its own and added it to ST’s Python’s sys.path. AAAPackageDev does this for example, in order to make it available to other packages. With the recently added possibility of 3., it is not necessary anymore.
3. Some packahge specified “pyyaml” as a dependency and Package Control made it available for all packages. See also packagecontrol.io/docs/dependencies

If you use 3. with your package, pyyaml will be downloaded for any ST version and the “yaml” module is available.