In MySQL, when using InnoDB, what happens to the way data is laid out on disk when the primary key is dropped?
If there is a not null unique key, that will be used as an internal primary key. If there is no candidate for a primary key, a 6-byte internal identified will be used as a hidden primary key that, unlike Oracle's ROWID, it cannot be accessed by the user.

As that implies that potentially an arbitrary value will be used to cluster the data, it is always recommended to have an explicit primary key.

When a new primary key is added, essentially the table (B+tree) is fully rebuilt around the new primary key value, including the secondary keys. That is why any ALTER TABLE operation involving the primary key will be very costly (and in MySQL 5.6 cannot be done online).