See -edit- for updated information

Normally states are added to the $stateProvider during the config phase. If you want to add states at runtime, you’ll need to keep a reference to the $stateProvider around.

This code is untested, but should do what you want. It creates a service called runtimeStates. You can inject it into runtime code and then add states.

// config-time dependencies can be injected here at .provider() declaration
myapp.provider('runtimeStates', function runtimeStates($stateProvider) {
  // runtime dependencies for the service can be injected here, at the provider.$get() function.
  this.$get = function($q, $timeout, $state) { // for example
    return { 
      addState: function(name, state) { 
        $stateProvider.state(name, state);
      }
    }
  }
});

I’ve implemented some stuff called Future States in UI-Router Extras that take care of some of the corner cases for you like mapping urls to states that don’t exist yet. Future States also shows how you can lazy load the source code for runtime-states. Take a look at the source code to get a feel for what is involved.

-edit- for UI-Router 1.0+

In UI-Router 1.0, states can be registered and deregistered at runtime using StateRegistry.register and StateRegistry.deregister.

To get access to the StateRegistry, inject it as $stateRegistry, or inject $uiRouter and access it via UIRouter.stateRegistry.

UI-Router 1.0 also includes Future States out of the box which handles lazy loading of state definitions, even synchronizing by URL.