The ideas that immediately come to mind are those cheap RF transmitter/receiver pairs that you can get on ebay for like $2, but i'm not sure of the range.
The range is poor to mediocre, depending on the antenna you create.
There's going to be a lot of these devices on the field, so I don't want them interfering with eachother.
Then, cheap radios are not the solution.
Other options are IR, Bluetooth, and ultrasonic sensors.
IR and ultrasonic won't distinguish one device from another. Ultrasonic won't even distinguish between the device, the ground, another player, etc.
I don't think I could get GPS modules cheaply enough, or accurate enough for this.
I don't either, but, if you do, let me know.
The second step is getting some idea of how far apart the two devices are.
Good luck with that.
To get an idea of the distance, the usual method is to send out a pulse at a known speed and see how long it takes to come back.
But, what did it come back reflected off of?
I don't think the arduino microprocessor is fast enough to do this with RF or IR. Would this be achievable with an ultrasonic transmitter and receiver?
Yes, but see comments above.
Are there any bluetooth modules that can be queried for signal strength?
Signal strength is a very poor indicator of distance.
I'm probably going to end up building these below cost
How? Or, did you mean that you will be selling/providing them for less than it costs you to make them?