Such a change can only occur if space becomes 4 dimensional instead of 3 dimensional (see for example, my answer here). That will have quite profound implications. For example,

The Riemann Curvature Tensor will have one more part (but this "part" means many more components) along with the Ricci Curvature Tensor and the Weyl Curvature Tensor. This actually related to the Electromagnetic force so in toher words, Gravity and EM will behave in the same way.

The 4+1=5 dimensional spacetime is actually unstable (agreedly, I don't know why, but whatever), at least according to Wikipedia's "privileged character of 3+1 dimensional spacetime" article.

The string theory landscape maybe a bit smaller (I think.).

The Ricci curvature in a vacuum on an Einstein Manifold would no longer be exactly $\Lambda g_{ab}$. There will be an ugly coefficient of $\frac{2}{3} $

The magnetic field could not be written as a vector, unlike the electric field. This is because it would have 6 components whereas the spatial dimension is only 4. So, perhaps humans would be more familiar with exterior algebras, earlier than us who live in 3+1=4 dimensions. Either that or we would be trying to find out how magnetism works. Or we would just die out, due to Implication (2).

Cross Products would be harder to evaluate. Another reason why we would be more familiar with exterior algebras!

Ok, so I'll come back to your question now:
So in 4D space the Newtonian gravitational force is: $$\vec F=G_5 \frac{m_1m_2}{r^3}$$ Here, $G_5$ is the gravitational constant in 4 spatial dimensions (5 spacetime dimensions, thus the 5 subscript.). It has to be different from the ordinary gravitational constant because it needs different units (since the $\frac{1}{r^3}$ immediately induces an extra units of $\operatorname{m}^{1}$, so the Gravitational constant needs to be adjusted to have a units with extra $\operatorname{m}$, i.e $\frac{\operatorname{m}^4}{\operatorname{kg} \operatorname{s^2}}$. According to string theory, the gravitational constant gets multiplied by the string length for every extra dimension added: $$G_5=\ell_s G_4$$
The exact string length is obviously unknown (a free parameter of string theory, as far as I know!) but let us just say it is $1.2374713757$ multiplied by the 3+1=4dimensional (i.e ordinary) planck length (it would be a coincidence if it were exact!). The 3+1=4dimensional planck length is approximately $1.616199\times 10^{35}$. Then, for the estimate, the string length would be approximately $2\times 10^{35}$ (now you know why I chose 1.2374713757 !:) (not a factorial sign )). Then, $G_5\approx 2\times 10^{35}\times6.673\times 10^{11}=13.346\times 10^{46}$
That is very weak gravity! Now, how heavy is an apple? It has a mass of say $0.1\operatorname{kg}$. Then, the gravitational force between that and the earth (in 5dimensional spacetime,/4dimensional space), is approximately around (after applying both the inverse cube proportion and the reduced, very weak, small, tiny, gravitational constant.),:: $$F\approx 4.82\times10^{32} \operatorname{Newtons}$$$$ And in daily life, it is like 1 Newton!..
Finally, in summary, gravity, would be much weaker!.
P.S. Also see this recent paper: http://arxiv.org/abs/hepph/0011014.