Very simple bluetooth requirement
Yes, this is as easy as you think it is!

Most integrated Bluetooth modules (modules that have a built-in stack, rather than HCI only which require you to use an external stack) will allow you to scan (inquire) for devices. I've been playing with several recently, the Bluegiga modules such as the WT12 have a particularly nice and easy to use serial interface. For those modules it's pretty much just a case of connecting to a UART, sending the inquire command down to the module and reading back the responses (a line per device found which includes the MAC address and device name).

Most of the modules I've seen have similar commands and interfacing. Expect to pay $20-40 for a module of this type.