After detecting my phone using WiFi (which does only work under Marshmallow while the phone is loading or the display is enabled) and detecting the fitbit device I came back to my original task to detect my phone using Bluetooth.
While there are many documents out there that describe this on different Linux and even raspberry variants none of those really worked for me. The raspberry 2 (Debian Jessie) seem to be a bit different there.
First of all you need a Bluetooth USB dongle. I buyed the Logilink BT00015 (available at amazon.com, amazon.de or elsewhere). I would expect that others work, too. But as always: On Linux, drivers can be tricky and it’s always good to know working hardware.