Follow this instructional video.
Grab the Gapps signed packages here
Tested April 2016
Alt solution, (untested)
1) genymotion 2.6.0
2) device emulator PREVIEW – Google Nexus 5X – 6.0.0 – API 23 – 1080×1920
3) flash Genymotion-ARM-Translation_v1.1.zip then restart.
4) flash gapps-L-4-21-15.zip. (https://www.androidfilehost.com/?fid=96042739161891406)
5) sign in into your google account.
6) flash ( benzo-gapps-M-20151011-signed-chroma-r3.zip) https://www.androidfilehost.com/?fid=24052804347835438 and restart.
Alt solution, tested
Alt downloads for Gapps
Notes: It seems you cannot use the open_gapps packages as they are not signed. Perhaps there’s a workaround but the method above works out of the box.