It will either be on the remote device, or os Signal's servers, depending on how the implementation works. Either way doesn't really matter; the whole point of encryption like this is to prevent third-party access to your communications.

It could be stored at NSA central for all it matters, and you'd still be the only one able to read the message (using the keys on your device).