The private key which signs a transaction is subject to paying fees for the execution of that transaction on the network.
For instance from the Ethereum white paper,
The term "transaction" is used in Ethereum to refer to the signed data
package that stores a message to be sent from an externally owned
account.
and
- a signature identifying the sender;
- the amount of ether to transfer from the sender to the recipient;
From this information we know that the sender
of a transaction is the externally owned account which signed it.
Furthermore the gas price which is more specific to your question,
Calculate the transaction fee as STARTGAS * GASPRICE
, and determine
the sending address from the signature. Subtract the fee from the
sender's account balance and increment the sender's nonce. If there is
not enough balance to spend, return an error.
This suggests that the gas is 'charged' to a sender of a transaction. Each full node who receives the transaction will ensure that it is well formed and update their internal state appropriately to reflect this change.
You'll need the server to sign the transaction with it's own key to allow them to pay the fees. A way around this could be by having the Ethereum user send the servers account enough ETH to cover the fees; then when the server accepts that this is valid, they can send the original tx to the network.
Hope this helps.