What gives the information? When there is a charge in space and then another charge is brought near it then it experiences a force but what gives this information to the first charge that there is another charge near it?
 A: The one-line, unsatisfying answer is "the electric field carries the information."
A more correct answer is that you can't really separate a charged particle from the electric field it creates.  When we introduce the idea of an electric field in an introductory class, we usually talk about charge as a property of matter and the electric field as a computational device for predicting how charges will interact with each other.
For example, we talk about how charge A will accelerate due the field produced by charge B, but how charge A doesn't sense its own field.  This approach allows us to use the simplifying assumption of point charges, but problematically suggests that somehow there is more than one electric field and each charge can tell its own field from those of its neighbors.
An equivalent way to describe the dynamics of a system of charges, and one that's less likely to give you headaches about how information gets from "here" to "there," is to think only about the electric and magnetic fields.
In this picture, a "point charge" is a computational device for keeping track of a $1/r^2$ electric field around a particular point in space.
The fields will tend to evolve over time into configurations that minimize the total energy, which is the integral of the energy density of the electromagnetic field,
$$
\frac{\mathrm dU}{\mathrm dV} = 
\frac12 \left(
\epsilon_0 E^2 + \frac1{\mu_0}B^2
\right),
\tag1
$$
but subject to the constraints imposed by Maxwell's equations which restrict how changes in the electromagnetic field at one point in space propagate to nearby points in space.
A useful hand-waving way to describe what happens is "the charges move so that the volume of the very strong fields becomes small."
(It's especially useful to note that the charge conservation equation is a consequence of the Maxwell equations, not an independent assumption: take the divergence of both sides of 
$$
\vec\nabla\times\vec B - \frac1{c^2}\frac\partial{\partial t}\vec E
= \mu_0 \vec J
\tag2
  $$
and see what happens.  Charge conservation is the most compelling reason we have to think of charges as the "physical" objects versus the computational devices, since charge can't or enter any volume of space without a corresponding current, but the field equation (2) actually carries more information than just charge conservation.)
So for instance, if you were to set up the scenario usually described as "bringing two opposite point charges near each other," what you're doing is setting up a region of very strong $\vec E$ between the locations of your two "point charges."
The total energy is reduced if the volume of strong field between the charges is reduced, so the charges tend to move closer to each other.
A person working from the perspective where charges are fundamental and fields are a computational device would say "the charges were attracted to one another"; a person working from a perspective where fields are fundamental and charges are a bookkeeping device would say "the field evolved into a lower-energy configuration."  Both are right.
Likewise for charges of the same sign: there's a zero in the field between them, and the total energy stored in the electric field is minimized if the two charges are far apart.
So the longer (and to me, more satisfying answer) to your question, 

When there is a charge in space and then another charge is brought near it then it experiences a force but what gives this information to the first charge that there is another charge near it?

is that both charges are shorthand descriptions of the electromagnetic field in region of space surrounding them both, and that the evolution of this field throughout space is governed by Maxwell's equations.
You can't "surprise" one charge with another one nearby.
