Are relationships maintained when you migrate records?

Yes. Relationships are maintained when using Monarch if related objects are moved in the same transaction.

When migrating records, do Record ID's remain the same or are new ID's generated?

New Record ID's are genrated. new record = new ID

The recommended Data Migration Apporach is a Siloed approach where you migrate more manageable pieces.