- what should I be looking for if I just want to relay a bit of info over long distances every so often?
You need to define how much data "a bit of info" is, and how often "every do often" is.
- do you need a "network" like verizon or something to use them? (I'm gonna guess no)
Guess again. Someone is paying for the network, and is going to charge you to use a share of it.
- how would an arduino communicate with one? Through spi, i2c, or what?
Which one? Most use SPI.
- anything else I should know?
This is not a newbie project.