When I `throw` something, where is it stored in memory?

Yes, the answer is compiler-dependent.

A quick experiment with my compiler (g++ 4.4.3) reveals that its runtime library first tries to malloc memory for the exception and, failing that, attempts to allocate space within a process-wide “emergency buffer” that lives on the data segment. If that doesn’t work out, it calls std::terminate().

It would appear that the main purpose of the emergency buffer is to be able to throw std::bad_alloc after the process has run out of heap space (in which case the malloc call would fail).

The relevant function is __cxa_allocate_exception:

extern "C" void *
__cxxabiv1::__cxa_allocate_exception(std::size_t thrown_size) throw()
{
  void *ret;

  thrown_size += sizeof (__cxa_refcounted_exception);
  ret = malloc (thrown_size);

  if (! ret)
    {
      __gnu_cxx::__scoped_lock sentry(emergency_mutex);

      bitmask_type used = emergency_used;
      unsigned int which = 0;

      if (thrown_size > EMERGENCY_OBJ_SIZE)
        goto failed;
      while (used & 1)
        {
          used >>= 1;
          if (++which >= EMERGENCY_OBJ_COUNT)
            goto failed;
        }

      emergency_used |= (bitmask_type)1 << which;
      ret = &emergency_buffer[which][0];

    failed:;

      if (!ret)
        std::terminate ();
    }

  // We have an uncaught exception as soon as we allocate memory.  This
  // yields uncaught_exception() true during the copy-constructor that
  // initializes the exception object.  See Issue 475.
  __cxa_eh_globals *globals = __cxa_get_globals ();
  globals->uncaughtExceptions += 1;

  memset (ret, 0, sizeof (__cxa_refcounted_exception));

  return (void *)((char *)ret + sizeof (__cxa_refcounted_exception));
}

I don’t know how typical this scheme is.