Currently, we view gravity as a fourth fundamental force, and theories such as LQG Loop Quantum Gravity and others below, are examples of attempts at fusing the Standard Model of particle physics, (which incorporates the other 3 fundamental forces) with gravity, in a synthesis called, unsurprisingly: Quantum Gravity.
So far, this fusion has not been achieved, either by String Theory, (which may be suitable as a quantum gravity theory contender depending, amongst other topics, as to how much importance you ascribe to Background Independence), nor by LQG, nor by another possible Quantum Gravity explanation: Twistor Theory.
One way around this issue is to postulate that gravity is not as fundamental as the Standard Model forces, but instead is a consequence of known fundamental interactions. The paper above both proposes this idea, and claims that if it is true, it may solve the dark matter mystery
To follow the idea, you need to know the fundamentals, and consequences of the 2nd Law of Thermodynamics, which underlies the concept of entropy. The idea here that gravity is related to entropy, as it is understood in terms of information contained within a system.
The more information required to describe a system, the more entropy it has.
Verlinde brings in the idea of the Holographic Principle to link thermodynamics and information. Moving the objects within a system, (stars, particles, galaxies, depending on the system), alters the entropy of that system and this can be linked to the information needed to describe the system, and thus it's entropy. Verlinde's paper describes what could be called an effective Entropic Force, that mimics gravity (as we currently understand it) and derives Einstein's equations of general relativity exactly.
An entropic force is an emergent phenomen
on resulting from the tendency of a
thermodynamic system to maximize its entropy. The system, or the set of macroscopic
variables describing it, tends to evolve from one state to another state that is statistically more
probable.
The problems with the idea of entropic gravity/force is that, because it describes exactly the same gravitational behavior as general relativity, it's obviously difficult to distinguish the two concepts. Crucially there is no currently known method of experimentally confirming Verlinde's idea.
Verlinde's idea involves a certain amount of what might be described as special pleading and this is demonstrated by requiring odd restrictions and behaviour of the system of masses, in terms of entropy, for Verlinde's idea to match the predictions of the universally accepted (and certainly extensively experimentally verified) General Relativity theory.
The first version of Verlinde's paper dealt with gravity produced by known and understood matter and the paper above now incorporates dark matter, which to some people may make it interesting , as current "mainstream" models of dark matter are still in the early stages of their development, with no definitive evidence for any particular model.
The new paper above calls attention to the fact that when we include dark matter in the calculation of entropy, we need additional information to describe a given spatial region. So our calculations of entropy as performed currently may require altertion. This new way of estimating entropy creates an additional entropic force, one that might help give more support to the original replacement for the effects of dark matter such as Modified Newtonian Dynamics (MoND). In effect, entropy may tie together gravity, dark matter and dark energy. It should be said that MOND is not generally accepted, for the reasons listed in the related link.
This is not a theory, it is an idea that possible experimentally testable models may be built on in the future. But the reasons for particular restrictions on calculations involving entropy, to make entropic force act as emergent gravity, still remain to be explained.
Also, modified gravity models have so far not be able to explain galaxy clustering, which General Relativity and the dark matter idea do explain. Obviously though, we still have a long way to go to explain dark matter itself.
Perhaps this work by Verlinde has its greatest merit in showing us that we should revisit, or at least always keep in mind, the 2nd Law of thermodynamics when considering explainations for little understood phenomena such as dark matter. After all, we still can't explain the low entropy conditions surrounding the Big Bang era, and this might imply that the role and significance of the 2nd Law of thermodynamics may need to be reconsidered.
This answer is my version of this Popular Science article, written as an attempt to understand the paper, (in as much I can).