1) 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.
2) 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.
3) how would an arduino communicate with one? Through spi, i2c, or what?
Which one? Most use SPI.
4) anything else I should know?
This is not a newbie project.