Like gravity, the electric force can do work and has a potential energy associated with it. But like we use fields to keep track of electromagnetic forces, we use electric potential, or voltage to keep track of electric potential energy. So instead of looking for the potential energy of specific objects, we define it in terms of properties of the space where the objects are.
The energy that the object gains or loses when traveling through a potential difference is supplied (or absorbed) by the electric field --- there is nothing else there. Therefore, it follows that electric fields contain energy.
To summarize: just as an electric field denotes force per unit charge, so electric potential differences represent potential energy differences per unit charge. A useful mnemonic is to consider a cell phone: the battery has the potential to do work for you, but it needs a charge! Actually, the analogy there is much more rigorous than it at first seems; we'll see why in the chapter on current. Since voltage is a quantity proportional to work it is a scalar, and can be positive or negative.