To my knowledge the relationship between the second law of thermodynamics and evolution is not as interesting as one might hope.
Firstly, evolution does not tell against the second law as noted in the other answers for the simple reason that life systems are driven by energy from the sun, or in the case of some deep sea life like the microbes and tube worms that thrive around undersea volcanic "smokers", they are driven by chemical energy and high-temperature heat from the volcanic material in a low-temperature icy abyssal environment. A good example of this is in Michael Brown's answer on crystal growth.
Indeed I would go further than this and say that one relationship between the second law of thermodynamics and evolution of life on Earth is that I think the latter, when you think of it as a grand experiment, or a grand simulation in the spirit of Douglas Adams's Earth-Designed-By-Deep-Thought, yields powerful support for the second law, maybe the strongest experimental evidence we have:
There are no biological perpetual motion machines of the second kind, and this is an extremely strong experimental null result
After 3 billion (and likely more like 4 billion) years of evolution, wherever biologists look, the basic powerhouses driving life (photosynthesis, mitochondrial ATP production from chemical energy ingested by cells and so forth) are well understood and almost certainly universal. It seems to me, that if there were a way around the second law through biological nanomachines (particularly with a variation on the Szilard engine, since the experiment cited in my footnote shows how it can scale to biological systems), evolution would almost certainly have found it by now and this second-law-violating process would be meeting all the needs of the creatures that evolved it. One could imagine that such creatures would swiftly become utterly dominant in the biosphere, sweeping all else aside. But this hasn't happened yet, although I believe there is an animal who delusionally believes that all its needs can be gotten for free from the environment, and that is just what that animal seems to be doing to the biosphere around it, so we have some anecdotal experiment evidence about how a second law violating animal might behave and how it might affect the biosphere. And yet, after all this time of life on Earth, all the creatures are using energy deriving processes altogether in keeping with the second law. Indeed the weird life (tube worms and the like) discovered in the last few decades around "volcanic smokers" deep in the ocean, almost poetically seem to be paying homage to Carnot's thought experiment, drawing work from heat and chemical potential blasting out of their central, hot life-giving "smoker" and casting the excess entropy out into the icy darkness surrounding their tiny thriving neighbourhood.
Part of your question seems to be can the concept of evolutionary fitness be meaningful independently of the concept of entropy? Or, could we have evolution in the if the second law didn't hold? Evolution and entropy are certainly related: you can't have evolution without minimisation of organism entropy (driven of course by the sun or volcanic smokers as noted above, such that the entropy of the total system still increases). To understand this, think of evolution as a search for fit creatures within a colossal "creature" configuration space: natural selection ends up confining the workable creatures to tiny neighbourhoods in this configuration space: if you imagine sampling a population of creatures, sequencing their DNA and working out an estimate for how many bits per creature defines that creature within the population, it will be a tiny fraction of the number of bits that can be encoded in each creatures genetic sequence. But I think this is independent of whether a decrease in creature entropy does or does not call for work as required by the second law of thermodynamics.
Footnote: An experiment wherein a working Maxwell Daemon was actually built and tested in the laboratory is described in:
Shoichi Toyabe; Takahiro Sagawa; Masahito Ueda; Eiro Muneyuki; Masaki Sano (2010-09-29). "Information heat engine: converting information to energy by feedback control". Nature Physics 6 (12): 988–992. arXiv:1009.5287. Bibcode:2011NatPh...6..988T. doi:10.1038/nphys1821. "We demonstrated that free energy is obtained by a feedback control using the information about the system; information is converted to free energy, as the first realization of Szilard-type Maxwell’s demon."