Answer:
You can program the NTX either right on the NXT "brick", or on your computer. Programming is pretty limited on the brick, but definitely fun for beginners. For example it takes a 3rd grader about 1 minute from step-by-step instructions to program it to tool around randomly while avoiding obstacles.
For more involved programs (and a bigger screen) you need to program on a computer and download your program to the brick. For that, you need to have a connection between your computer and the NXT. That can either be via standard USB cable, or Blue-tooth if your computer has it.
NXT comes with a graphically based programming language called NXT-G. (For geeks: NXT-G supports subroutines & multi-threading, variables are global.) In addition there are currently (as of 2012) about 15 other languages/APIs available for the NXT , including standards like C and Java. Some are free, others around $50. (NXT can only handle one language at a time, so you have to initialize your brick to receive a different language. To reinitialize your brick with the original NXT-G you have to be connected to the Internet and the brick at the same time. At least that's how I did it.) See a list of languages here:
http://en.wikipedia.org/wiki/Lego_Mindstorms_NXT_2.0
OK let's assume you're gonna use NXT-G, you are connected and have the NXT-G programming environment installed on your computer, so what's next? ...See the NXT maual for simple step-by-step. If you don't have it I'm sure its online, and there is a lot more; you can start with:
http://legoengineering.com (stay on NXT-G, ignore ROBOLAB).
Have fun!!