解決にかなりの時間をくってしまったので備忘メモ。
(※2015/06/17時点 Unity5.0.2f1での情報です)

Unity Editor上だとParseと通信出来ていたのに、Android実機だとParseと通信出来ず下記のようなエラーが発生しました。

I/Unity(5080): MissingMethodException: Method not found: 'Default constructor not found...ctor() of Parse.PlatformHooks'.
I/Unity(5080):   at System.Activator.CreateInstance (System.Type type, Boolean nonPublic) [0x00000] in <filename unknown>:0 
I/Unity(5080):   at System.Activator.CreateInstance (System.Type type) [0x00000] in <filename unknown>:0 
I/Unity(5080):   at Parse.ParseClient..cctor () [0x00000] in <filename unknown>:0 
I/Unity(5080): Rethrow as TypeInitializationException: An exception was thrown by the type initializer for Parse.ParseClient
I/Unity(5080):   at Parse.ParseInitializeBehaviour.Initialize () [0x00000] in <filename unknown>:0 
I/Unity(5080):   at Parse.ParseInitializeBehaviour.Awake () [0x00000] in <filename unknown>:0

Stripping Levelが臭いかも？と思ったのでAndroidの
Player Settings→Other Settings→Stripping Levelを「Disabled」に変更してみたところ、エラーが変化。

I/Unity(6634): AndroidJavaException: java.lang.ClassNotFoundException: com.parse.ParsePushUnityHelper
I/Unity(6634):   at UnityEngine.AndroidJNISafe.CheckException () [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJNISafe.CallStaticObjectMethod (IntPtr clazz, IntPtr methodID, UnityEngine.jvalue[] args) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJavaObject._CallStatic[AndroidJavaObject] (System.String methodName, System.Object[] args) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJavaObject.CallStatic[AndroidJavaObject] (System.String methodName, System.Object[] args) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJavaObject.FindClass (System.String name) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJavaClass._AndroidJavaClass (System.String className) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at UnityEngine.AndroidJavaClass..ctor (System.String className) [0x00000] in <filename unknown>:0 
I/Unity(6634):   at System.Reflection.MonoCMethod.Invoke (System.Object obj, BindingFlags invokeAttr, S

ClassNotFoundExceptionて。。PUSH通知周りのClassが足りんらしいです。
Parse公式のUnityのBlank Projectをベースにいじってるのに何故こんなエラーが出るんだろう、と散々調べまわった結果が↓。

[解決策] Asset StoreからParseのAssetを入れよう

結論、コレだけ。

Parse公式サイトからUnityのBlank Projectが落とせますが、現時点(v1.5.2)ではこれをベースに進めようとするとマルチプラットフォーム対応でハマります。
（Android実機で前述の問題が出てしまいます）

ParseのAssetはその辺も考えて作られているようなので、素直にこちらを使うのが吉。
もちろん無料です。

Assetを入れた後にやること

Assetを入れたらPlugins/Android/AndroidManifest.xml開いて下記の記述を探します。

<activity android:name=".UnityPlayerActivity">

このままだとActivityが見つからずエラーになるので、

<activity android:name="com.unity3d.player.UnityPlayerActivity">

に変更します。これで万事OK。
ちなみに、このあとStripping Levelを「Use micro mscorlib」に戻してもちゃんと動きました。