YES! IT IS POSSIBLE!
Most VPN Providers "provide" you an IP (like a Proxy). They also encrypt your connection through the internet so that your login (for example) is encrypted!
Even that this may prevent hackers or the authorities from spying you, most VPN Providers keep logs (for some days or weeks) to prevent hackers. What this means is that if the Authorities ask them to disclose your Internet activity, they will do so.
I think that only nVPN (http://nvpn.net) doesn't keep logs and protects you from the authorities. (However, you need to pay to use their VPN...)
What you said about if they use AES encryption, it is up to them what encryption they use. Among others, AES is one of the strongest encryptions available, however, secure = slow, so they can use other less secure encryption algorithms in order to guarantee speed.
Thus, hiding your activity on the Internet using VPN is possible!