Faits: Faits: A. Ressortissant de Bosnie et Herzégovine né en 1982, marié à une Suissesse, X._ a été condamné, le 16 février 2005, à une peine de 16 mois d'emprisonnement avec sursis pendant trois ans pour vol, tentative de vol, vol en bande, dommages à la propriété, violation de domicile et vol d'usage et à l'expulsion du territoire suisse pour une durée de trois ans avec sursis pendant trois ans. Le 2 février 2006, l'Office fédéral des migrations a rendu à l'égard de X._ une décision de refus d'approbation à l'octroi d'une autorisation de séjour et de renvoi de Suisse. Par acte daté du 1er mars 2006, le prénommé a recouru contre cette décision auprès du Département fédéral de justice et police (ci-après: le Département). Par lettre signature du 16 mars 2006, le Département a imparti à X._ un délai échéant le 24 avril 2006 pour effectuer une avance de frais de 700 fr. Le courrier indiquait que si l'avance n'était pas faite dans le délai, le recours serait déclaré irrecevable. Au terme du délai de garde, l'office postal a retourné ce courrier à l'expéditeur avec la mention « non réclamé ». Par acte du 27 avril 2006, X._, désormais représenté par un avocat, a complété son recours. Il a demandé à pouvoir consulter le dossier et qu'un délai lui soit octroyé pour déposer un mémoire complémentaire. Le 2 mai 2006, le Département a rendu une décision par laquelle il a déclaré le recours de X._ irrecevable en raison du non-versement de l'avance de frais et mis à sa charge les frais de procédure. Dans la motivation, il a constaté que la demande tendant à la consultation du dossier et à l'octroi d'un délai pour le dépôt d'un mémoire complémentaire était devenue sans objet. Le 2 mai 2006, le Département a rendu une décision par laquelle il a déclaré le recours de X._ irrecevable en raison du non-versement de l'avance de frais et mis à sa charge les frais de procédure. Dans la motivation, il a constaté que la demande tendant à la consultation du dossier et à l'octroi d'un délai pour le dépôt d'un mémoire complémentaire était devenue sans objet. B. Agissant par la voie du recours de droit administratif, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler cette décision et d'inviter l'autorité intimée à traiter le recours sur le fond. Il demande également que son recours soit doté de l'effet suspensif. Il prétend que la lettre signature du 16 mars 2006 ne lui a pas été valablement notifiée et soutient que le Département n'aurait de toute manière pas été en droit d'exiger le versement d'une avance de frais. Il dénonce également une violation de son droit d'être entendu. Dans sa détermination du 16 juin 2006, le Département conclut implicitement au rejet du recours. Par ordonnance du 3 juillet 2006, le Président de la IIème Cour de droit public a admis la requête d'effet suspensif.