As far as I know yes. Everything I have read indicates that Amazon stripped C2DM support out of the Fire. I know right? If you or your users are willing to root it, installing Google services is an option.
Urban Airship has a push service named Helium which purportedly works with Kindle Fire. I have yet to be able to try it though.
Update 8/13/2013
There is also Amazon SNS. There is a great blog on the topic.
See this code snippet for how to implement a receiver ( from the Amazon Web Services blog):
public class ExternalReceiver extends BroadcastReceiver {
@Override
public void onReceive(Context context, Intent intent) {
Log.i("ExternalReceiver","onReceive");
Bundle extras = intent.getExtras();
StringBuilder payload = new StringBuilder();
for(String key : extras.keySet()){
payload.append(String.format("%s=%s", key, extras.getString(key)) + '\n');
}
Intent newIntent = new Intent();
newIntent.setClass(context, AndroidMobilePushApp.class);
newIntent.putExtra(context.getString(R.string.msg_field), payload.toString());
newIntent.setFlags(Intent.FLAG_ACTIVITY_NEW_TASK | Intent.FLAG_ACTIVITY_SINGLE_TOP);
context.startActivity(newIntent);
}
}