I'm looking for the most elegant way to notify users of my library that they need a specific unix command to ensure that it will works...
When is the bet time for my lib to raise an error:

Installation ?
When my app call the command ?
At the import of my lib ?
both?

And also how should you detect that the command is missing (if not commands.getoutput("which CommandIDependsOn"): raise Exception("you need CommandIDependsOn")).
I need advices.
I wouldn't have any check at all. Document that your library requires this command, and if the user tries to use whatever part of your library needs it, an exception will be raised by whatever runs the command. It should still be possible to import your library and use it, even if only a subset of functionality is offered.
(PS: commands is old and broken and shouldn't be used in new code. subprocess is the hot new stuff.)
How to depends of a system command with python/distutils?