Can a permanent magnet attract things permanently? If yes, then doesn't it violate law of conservation of energy? If it CAN attract permanently then it can continuously give kinetic energy to magnetic objects by attracting them. I found answers about this stating that WE supply potential energy to the magnetic materials by pulling them apart from the magnet. But, where did they get the energy in the very starting? Suppose that if I bring a magnet from market and keep it near an iron nail. The energy I gave the magnet to bring it from the market converts into heat on stopping it. So how does the iron nail gets the energy?
 A: You can ask the same question about gravity or electric charge. Where does the asteroid get its energy from when it is captured by the earth's gravitational field and crashes into the earth?
The asteroid gains its kinetic energy from its gravitational potential energy and similarly the magnet gains its energy from its magnetic potential energy.
How did this potential energy arise? There are various ways (e.g., as you said, pulling them apart), but the ultimate answer is that the universe started in a state of low entropy (high order) and is moving to a state of higher entropy (disorder). The change in entropy allows work to be done and energy to be extracted. Essentially, the universe started in a state where energy was available to be used and it has been shuffling it around ever since.
A: One minor thing that will help is that no object has potential energy on its own.  Potential energy comes from the structure of how objects are found in space.  We do indeed sometimes say "this object has gravitational potential energy," but what we really mean is that there is potential energy in the system of the Earth and the object.  It's not actually energy "owned" by either object.  The former is easier to say, but the latter is more technically correct.
I point to the more technically correct version because it talks about a system, and indeed it is the larger system of the whole world you have to look to for where that energy came from.  Some of it came from plate tectonics moving the iron ore further away from the ore that created the magnet (from the thermal energy of the planet).  Some of it might have come from the delivery truck that moved it to the store (from the chemical energy of the gasoline), if that delivery truck happened to have to go closer to your house before reaching the store.
Some of it may have even come from other magnets which you aren't even thinking about which may have had a larger pull on the iron nail than your magnet.  Remember, magnetic forces decrease by the cube of the distance (faster than electrostatic forces, which decrease by the square of the distance).  Even a very small magnet in the store will pull on your nail harder than your magnet does.
Indeed, eventually you can trace that energy all the way to the big bang, but typically we stop before then.  If you really do the math, you find that almost all of the potential energy in the configuration is found by the nail being further than just a few centimeters away from the magnet.  The difference in potential between the nail being, say, a meter away and 10 kilometers away is tremendously small.  Small puffs of air in the wind contain more far energy than that.
So really, most of the question can be reduced to "why is the nail more than a few centimeters away from the magnet in the first place?"  If you answer that question, you answer almost the entire question of where did the energy come from.
A: Let me start by saying it's a very difficult mathematical job to calculate the force between macroscopic magnets. See this Wikipedia article. But I'll try to explain in words why conservation of energy isn't violated as you ask in the question body.
Say we start with one magnet. Now say we put a lot of magnets (or substances that react to it by getting magnetized by the magnet, say an iron nail) around it.
All the magnets will experience a torque and their north poles will be aligned with the magnets south pole and vice-versa and will start to move to one of the two poles (depending on their position to the magnet).
The non-magnetic substances which can be magnetized by the magnet develop a north- and south pole, also dependent on their position relative to the magnet.
So all these objects will move towards each other by magnetic dipole interaction. Just throw little magnets randomly on a smooth table around a big one together with non-magnetic substances that the magnet can magnetize.
So all objects around the central magnet acquire a momentum (inclusive the magnet you start with). If the total momentum of all the objects is initially zero, so the final compound of magnets and nails is zero (one can always choose a center of mass frame where this is the case). The energy contained in the field lines emerging from this new complicated magnet has decreased (the kinetic energy of all the elements rushing towards and colliding with each other is converted in heat and vibrational energy of the compound; the collision between two magnets or nails is not elastic).
Now the total energy contained in the magnetic field of the newly formed magnet (the compound of all magnets and nails) is less than all the magnets and nails (which have a zero magnetic field energy around them, on their own) apart. This is, by the way, the opposite of separating two magnets which results in higher magnetic field energy surrounding the magnets. This lower energy is not caused by the increase in temperature or the vibrations in the colliding magnets and magnets, as might be obvious (only very high temperature differences or huge vibrations might do this trick).
Because the magnetic field energy contained around the compound it will interact less with newly brought magnets and nails put around it. But again a new compound will emerge, with as result a new compound that has less magnetic energy contained around it than all the earlier formed compound and newly brought in magnets and nails (which are clearly man-made) apart. And because the magnetic force is proportional to $\frac{1}{r^3}$ the force is diminishing fast. With the result that the magnetic field surrounding the magnets and nails will acquire less and less energy than the composing parts on their own so even if a permanent magnet attracts permanently nails and other magnets it doesn't provide an infinite amount of energy.
Even if you bring together (as a Gedanken Experiment, for it is clear that in reality, this is impossible) all the magnets, nails and other magnetizable stuff in the Universe (no matter how they came to be, and come into being, like the huge magnets on the surface of the sun, assuming these won't destroy the little magnets and nails, man-made superconductors with an accompanying magnet, all electron spins or orbital momenta, etc.), the potential energy contained in the magnetic field lines of the whole is less than that of the elements building up the whole. So conservation of energy is not violated. If only...
Now from where gets your nail its potential energy, which is less than the non-magnetized nail, so closed magnetic field lines can develop inside and outside it? Of course, that depends on where you place it (near magnetic field lines, far away from them, or somewhere in space where no magnetic fields are present). In a somewhat similar way, permanent magnets got their potential energy from the coming together of the atoms forming the ferromagnetic material. All electrons that are unpaired in the atom orbitals align themselves, thereby reducing the internal potential energy, whilst forming closed magnetic field lines. On the outside of the magnet from north to south and on the inside from south to north, so the line is closed.
Here you can see a nice video about a (man-made) magnetic river. Just for fun and it is something you can learn from too!
