The machine that shows the contractions when you're giving birth?

A CTG (cardiotocograph) machine. Measures the baby's heart (cardio) and the mother's contractions (toco).

I remember when my daughter was born that the machine was informally called "the monitor," as in "Um, nurse? Could you stop the monitor from making that incessant beeping?"

And what do you call the paper that the above machine spits out?

A cardiotocogram. As to the name for just the paper, ask the manufacturers.

Again, this was referred to casually as "the strip," as in "Boy, after 20 hours of labor you've got a pretty long strip going there!"