How do I determine an optimal or above average fee to gain priority in the network during a transaction?
The amount you should pay is constantly changing, so you'll have to check at the time you send the transaction. 21 has an API that provides recommendations on mining prices.

They are only recommendations though, there isn't really a definitive answer. The network could get flooded with higher fee transactions at any time, and your fee would then appear relatively low to miners. If you need to be absolutely certain you may want to raise the fee even further, but I believe they've taken some amount of that into account.