Should I inherit from std::exception?

Yes you should derive from std::exception.

Others have answered that std::exception has the problem that you can't pass a text message to it, however it is generally not a good idea to attempt to format a user message at the point of the throw. Instead, use the exception object to transport all relevant information to the catch site which can then format a user-friendly message.

Whether to derive from any standard exception type or not is the first question. Doing so enables a single exception handler for all standard library exceptions and your own, but it also encourages such catch-them-all handlers. The problem is that one should only catch exceptions one knows how to handle. In main(), for example, catching all std::exceptions is likely a good thing if the what() string will be logged as a last resort before exiting. Elsewhere, however, it's unlikely to be a good idea.

Once you've decided whether to derive from a standard exception type or not, then the question is which should be the base. If your application doesn't need i18n, you might think that formatting a message at the call site is every bit as good as saving information and generating the message at the call site. The problem is that the formatted message may not be needed. Better to use a lazy message generation scheme -- perhaps with preallocated memory. Then, if the message is needed, it will be generated on access (and, possibly, cached in the exception object). Thus, if the message is generated when thrown, then a std::exception derivate, like std::runtime_error is needed as the base class. If the message is generated lazily, then std::exception is the appropriate base.

Though this question is rather old and has already been answered plenty, I just want to add a note on how to do proper exception handling in C++11, since I am continually missing this in discussions about exceptions:

Use std::nested_exception and std::throw_with_nested

It is described on StackOverflow here and here, how you can get a backtrace on your exceptions inside your code without need for a debugger or cumbersome logging, by simply writing a proper exception handler which will rethrow nested exceptions.

Since you can do this with any derived exception class, you can add a lot of information to such a backtrace! You may also take a look at my MWE on GitHub, where a backtrace would look something like this:

Library API: Exception caught in function 'api_function'
Backtrace:
~/Git/mwe-cpp-exception/src/detail/Library.cpp:17 : library_function failed
~/Git/mwe-cpp-exception/src/detail/Library.cpp:13 : could not open file "nonexistent.txt"

You don't even need to subclass std::runtime_error in order to get plenty of information when an exception is thrown.

The only benefit I see in subclassing (instead of just using std::runtime_error) is that your exception handler can catch your custom exception and do something special. For example:

try
{
  // something that may throw
}
catch( const MyException & ex )
{
  // do something specialized with the
  // additional info inside MyException
}
catch( const std::exception & ex )
{
  std::cerr << ex.what() << std::endl;
}
catch( ... )
{
  std::cerr << "unknown exception!" << std::endl;
}