These modules usually work with Arduino as they are all base on some HC-XX submodule. HC-03/05 are fairly easy to configure and use, flexibility is OK but as most other modules limited to the serial profile.
HC-06 based modules seems to be a bit more limited but I never used such a module, so I have no experience with it.
The problem is, that all versions are sold as JY-MCU so you probably don't know what you get before your hold it in your hands.
ATtiny is not a principal problem if you get your code into the limited flash.
Those JY-MCU modules are definitely the cheapest for a wireless communication link, but they suck in terms of documentation. You can buy them if you just need to send some data to your PC, but if you want to do anything more, like changing between master and slave mode, have fun! The Bluetooth modules based off the RN-42 such as the BlueSMIRF silver are much easier to use but cost $15 for the bare module and $40 from Sparkfun for a breakout board.