Understanding migrations and CLI commands
How does craft know which migrations have been applied and which are new? I.e. Is it by comparing the craft_migrations table to the migration files found in '/vendor/craftcms/cms/src/migrations' folder (or plugin folders)?

Exactly!

Where does the information from running 'php craft migrate/new' and 'php craft migrate/history' come from?

migrate/history purely checks the migrations table in the database for a list of migrations that have already run.
migrate/new grabs the same list of migrations from the database that migrate/history does, then compares it again the migrations folder on the file system to find any newer migrations (using the timestamp in the filename) that haven't run yet and returns that list.

So clearly something is out of sync (or is terribly wrong in this project).

Something does sound out-of-sync to me.

How are version numbers and migrations associated with each other?

Craft's (and a plugin's) version number is independent of migrations. Both have a separate concept called a schemaVersion, and when that number gets incremented, that tells Craft that a plugin (or itself) that there are new migrations that need to run.

What determines the order that migrations are run?

They are sorted, but since timestamps are embedded in the migration names, they will run from the oldest unapplied migrations to the newest unapplied migrations.

Finally, if a migration fails, is there something else that should be done besides restoring the DB to reset the craft state, before attempting to run migrate/all again?

Nope - restore from a pre-update attempt database back, fix whatever caused it to fail, then try again.