The Linker won't necessarily directly complain about memory over "drafts," so you have to watch it. What you usually get when you run out of space is a link error about not being able to load one of the libraries at the end. As reported by MPLab and the linker you will actual have less memory available to you due to other system overhead. As I recall the MAP file will report ~97% utilization when it is actually full.
We have three types of memory on the RC available to use.
See
http://www.ifirobotics.com/rc.shtml#Specifications for the PIC18F8722
128,000 bytes program space
3936 bytes variable space (less the PROTECTED, etc. areas listed in 18f8722.lkr)
1024 bytes EEPROM
The default is to put variables into the 3936 byte variable space where your code can modify the values while it's running. There is a further limitation on the variable space due to how the linker has the space blocked out.
You are only able to declare 256 bytes of variable space in any one MPLAB project file.
"rom" puts your stuff into the 128K program space, but you cannot change values placed here as you noted. They are fixed and read-only when your code runs. As you said it is probably the best place for our fixed lookup tables.
The EEPROM requires special runtime reads/writes to use, but it is maintained even when your robot power is off.
In MPLAB you can also check on your memory utilization via: View -> Memory Usage Gauge
Note though that the Program memory is stated in two-byte words, not bytes for some reason.
P.S. We've kept our autonomous modes in large arrays in program space since these PIC RCs came out in 2004.