Where does InnoDB store transaction data before committing it?
"Where is uncommitted data stored, such that a READ_UNCOMMITTED transaction can read uncommitted data from another transaction?"

The new uncommitted record (clustered PK) versions are treated as the "current" version of the record on page. So they can be stored in the buffer pool and/or in the tablespace (e.g. tablename.ibd). Transactions that then need to build a snapshot/view in anything other than READ-UNCOMMITTED, need to construct a previous version of the row (following the history list) using the UNDO records (stored in the system tablespace). When reading the uncommitted record, InnoDB may also need to read some uncommitted secondary index records from the Change Buffer and apply them before presenting the record back to the user. 

It's this behavior that can make rollbacks in InnoDB relatively expensive. It's the big factor that can also lead to potential performance issues from long running idle transactions that are holding updated records, as those transactions will block purge operations and the history list of old record versions grows, and the UNDO records needed to rebuild those old versions on-demand, will continue to grow. It slows down new transactions that need to read an older/committed version of the record, as they need to traverse a longer and longer history list--which is a singly linked list of UNDO records--and do more work in order to reconstruct the old version of the record. So you end up using a lot of CPU cycles (not to mention internal locking primitives: mutexes, rw_locks, semaphores, etc.) on non-user visible work that slows down query processing.

Hopefully that makes sense? :)  

As an FYI, in MySQL 5.7 you can move the UNDO tablespace and logs out of the system tablespace, and have them automatically truncated. They can grow quite large if you have a long running transaction that prevents purge operations, resulting in a very long and ever growing history list length. Having them stored in the system tablespace was the single most common cause of a huge/growing ibdata1 file, which in turn cannot be truncated/shrunk/vacuumed in order to later reclaim that space.