内容的には、 Android - Genymotionの仮想端末に Google Play をインストール とほぼ同じ、違う点は Lollipop(v5.1) になった点。

GenyMotion をインストール

(省略)

仮想環境を作成

とりあえず

• Android version: 5.1.0
• Device model: Google Nexus 4

で作成

ARM Translation をインストール

android - How do you install Google frameworks (Play, Accounts, etc.) on a Genymotion virtual device? - Stack Overflow

上記ページの "ARM Translation Installer v1.1 Hosted by FILETRIP" のリンクからダウンロード

※オリジナルは以下のサイトだが、リンク等は上記が新しい

[GUIDE] Genymotion | Installing ARM Translat… | Android Development and Hacking | XDA Forums

Google Apps for Android

同じページの "Google Apps for Android 5.1" のリンクから Google Apps の zip ファイルをダウンロード。

念のためダウンロードした zip の MD5 をチェック

$ md5 path/to/gapps-5.1-2015-04-20-15-56-24.zip

ARM Translation 及び Google Apps for Android のインストール

インストールは ARM Translation -> GApps の順番に、ダウンロードした zip ファイルを Genymotion の仮想端末のウィンドウにドラッグ＆ドロップでOK

インストールしたらPlayストアのアイコンタップして起動できたら完了。