If I set up a VPN, does *everything* go over it? If I set up a VPN connection for Android, what gets routed over the VPN?  Just web browsing?  All internet connections from all apps?

In Cyanogenmod, in the Add OpenVPN config, "Advanced" settings, there is an option for "Redirect gateway - Force all traffic to berouted thru the VPN tunnel", which is off by default.

With this off, which apps/communications get routed through it?

The other VPN types do not have this option.  Do they work this way or not?

After setting up a VPN, how can I verify that it's working?
The setting that you're talking about is in effect the --redirect-gateway option of OpenVPN and is documented on the OpenVPN man page


  --redirect-gateway
  
  Automatically execute routing commands to cause all outgoing IP traffic to be redirected over the VPN.
  
  
  
  This option performs three steps:
  
  
  Create a static route for the --remote address which forwards to the pre-existing default gateway. This is done so that (3) will not create a routing loop.
  Delete the default gateway route.
  Set the new default gateway to be the VPN endpoint address (derived either from --route-gateway or the second parameter to --ifconfig when --dev tun is specified).
  
  
  When the tunnel is torn down, all of the above steps are reversed so that the original default route is restored.


The routing of all network connections occurs at the system level. Only apps that have the ability to modify the routing table of the device to use a different gateway than the default can bypass the VPN. Theoretically any app with SuperUser access could do this.