HMAC-SHA1: How to do it properly in Java?

Recommend Apache Common Codec Library, quite simple and easy to use. HmacUtils.hmacSha1Hex(key, string_to_sign);

On your PHP side, use single-quotes around the key so that the $ character is not treated as a variable reference. i.e.,

hash_hmac("sha1", "helloworld", 'PRIE7$oG2uS-Yf17kEnUEpi5hvW/#AFo')

Otherwise, the key you really get is PRIE7-Yf17kEnUEpi5hvW/#AFo (assuming the variable $oG2uS is not defined).