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.
Given that you can replace the arduino for under $30 (or for about $5-6 if the atmega chip is socketed, or a mere $3.50 for a blank atmega you can initialize on a breadboard using the arduinoISP sketch before you fry the current one), if you are more interested in learning about things, I'd say go ahead and build some driving circuits. On the other hand, if you just want to "make it go" buy someone's driver shield or serial-controlled driver module.
As an aside, "9v" batteries have very little current capacity and are not intended for motors - using one with a motor will cause it's voltage to sag severely, and it will run down quickly. Most of the components in your toy are connected in parallel - the 9.6v battery (probably consisting of 8 AA-size NiCd or NiMH cells) probably powers the drive motor directly, and the servo and perhaps electronics through a voltage regulator of about 5 volts (at least if they are standard parts). You should probably keep that scheme.
There are some things you can do to "protect" the arduino such as using opto-isolators (essentially an LED and a phototransistor molded in an IC-like package - you can make your own with discrete parts and heat shrink tubing) to transfer signals between the arduino (or radio receiver) and the servo and drive motor without their being any electrical connection between the two - each in that case requiring its own battery. However, most budget equipment simply relies on careful design and filters to suppress spikes, supply noise, and RFI. Amongst things you will see in R/C vehicles:
small capacitors across the terminals of motors, and/or between each terminal and the motor case
if the motor is unidirectional, a reversed diode across the terminals, if it is bidirectional four reversed diodes between the two motor terminals and two battery terminals.
Most likely you can work out a solution running everything off the same battery if you power the motor directly, run the servo off of its own 5v regulator, and run the arduino off of its on-board 5v regulator. Alternatively, you can give the arduino its own battery (perhaps 3 AAA's if you bypass the regulator) and establish a common ground connection between that and the motor/servo battery.
In terms of driver circuits for the main motor, the big question is if you are okay with forward only, or if you need forward and reverse. Related questions are PWM duty cycle speed control, electronic braking, and efficiency.
For a small toy with forward-only, you can simply use an medium sized NPN transistor as a switch in the negative lead (emitter to battery -, collector to motor -), with the base connected via a resistor to an arduino pin. A pragmatic approach would be to start with a large resistor such as 10K ohms and reduce the resistance just until the voltage drop across the transistor is reduced to about .6v - implying it is fully "on" and most of the battery voltage is available to the motor.
Doing forward-reverse control is more complicated - typically accomplished with an "H bridge driver" in which each leg of the motor can be connected to the negative battery terminal via an NPN transistor or the positive terminal via a PNP. Two control pins are required - 01 is one direction of rotation, 10 the other, while 00 and 11 both stop the motor. Building H bridges is a bit tricky - you have to be sure that the biasing is such that the NPN and PNP transistor on a side can't both be on at once and short out the power supply, but there are packaged solutions such as the L293 and L298 (which handles two motors).
Bipolar transistors do have substantial loss at low voltages, so higher performance vehicles typically use MOSFETs, but these are trickier to work with (especially in an H bridge configuration) and handle (they are subject to damage from static or overvoltage).
Best Answer
I would suggest two options.
First - and this involves a small amount of wiring and soldering - using a PowerSwitchTail II. This is a very safe way of switching mains voltage. There is adequate isolation, it is safely cased and tested.
If you really want to do no wiring or soldering at all, then I would suggest finding one of the common 434/868/915MHz (depending on region) remote controlled sockets using a basic OOK protocol, and buy a simple 434MHz transmitter. A number of the protocols are documented in various places. The only issue with these is that you have no sure way of knowing if the switch is on or off.