For one, you can handle the app class as an object itself.

The only method that needs to be static in your code is the main function. Everything else doesn't need to be. Within the main class, you can instantiate an "app" object and then starting your program from there. You can completely get rid of the need for static methods if you do something like this:

public static void main(String[] args) {
    App changeApp = new App();
    changeApp.startProgram();  //or could be in the constructor of App class
}

You can also split up a lot of your code into multiple classes. You can put a lot of IO code into a separate class, and anything involving change into another separate class. The app class would be entirely focused on things like displaying a menu, and controlling the app logic. Finally, you can also put your constants in another class.

I don't think you need any regular expressions for the input. You can just use the scanner class to get the necessary input.

Your giveChange() method can be simplified a lot, too.

The algorithm to work out the correct amount of coins can be simplified:

changeOwed = amountPaid - productPrice;
int coinCount = 0;

while(changeOwed > 0)
{
    if(coinStack.peek() > changeOwed)
    {
        changeOwed -= coinStack.peek();
        coinCount++;
    }
    else
        coinStack.pop();
}  

return coinCount;

coinStack is just a stack of the possible coins.

another solution:

changeOwed = amountPaid - productPrice;
int coinCount = 0;

for(int coin : coins)
{
    if(coin <= changeOwed)
    {
        coinCount += changeOwed / coin;
        changeOwed %= coin;
    }
}

return coinCount;

The other big issue I see with your code is the usage of doubles for representing currency. This is a huge no-no. In fact, you could easily represent all of the values as ints if you wanted to. Just multiply everything by 100 and now you no longer need to worry about decimals. 1p is now 100, and 1/4p goes from .25 to 25. You actually did the opposite of that by handling 1p as .01.