How does Darwinian Evolution work?
I accidentally wrote a lot!

I first discuss the term Darwinian evolution. I then describe the main evolutionary processes insisting on the two elements of interest in your question, that is mutations and natural selection. In the end, I directly address your two statements and bring a few more complications into the subjects.

Did you say Darwinian evolution?

Evolution is more than Darwinian evolution

The expression "Darwinian evolution" easily yield to misunderstandings. Darwin was probably the most important scientist and one of the first (if not the first) to develop the theory of evolution but evolutionary biology today is so much more than Darwin's theory of evolution.

Examples of very basic things Darwin did not know


We discovered the structure of DNA in the 1950s-1960s only with Miesher, Chargaff and most renowned Watson and Crick (history of the discovery). Darwin had no idea of the existence of DNA and had not even hypothesized about the existence of such a molecule (which came first by Erwin Schrödinger).
Darwin was not aware either that inheritance was through the transmission of "particles/atomic" and not through the inheritance of some kind of "fluid/continuum". In other words, Darwin did not know the Law of Segregation by Gregor Mendel (even if they lived in the same epoch).
Darwin had no idea about Evo-Devo, that is he had no idea about the similitudes in developmental processes among related (even distantly related) organisms.
Globally speaking, while Darwin managed to touch a little bit about many of the subjects of modern evolutionary biology (which is very impressive), he only manages to mention them and failed to provide any prediction. This is a large part because no one had no concept in genetics at that time.


Evolution is more than natural selection and mutations

Evolution is not only about natural selection. Even C. Darwin knew that evolution is way more than natural selection. It is for example very important to consider random events. One of them is mutation, another is genetic drift (I am not trying to list every process that influence evolution but only to give you a sense of why natural selection is different than evolution with a goal of explaining why a trait that is needed do not necessarily appear). Both mutations and genetic drift explain why a species will not necessarily be perfectly adapted to its environment. Evolutionary biology is a big field of knowledge and there is a lot to know about evolutionary processes.

Natural Selection and Mutations explained by the Lewontin Recipe

The Lewontin's recipe is a good way in order to understand what is natural selection and when it occurs. The Lewontin's recipe says that natural selection occurs whenever:


Individuals in a population vary in terms of a given trait
This trait has some (additive) heritability. Here is one of the several posts that explain the concept of heritability. It might be slightly a post that is a bit advanced for you though but shortly speaking it means that offspring are more similar to their parents more than they are to other non-kin individuals in the population.
The fitness varies (not necessarily linearly) as the trait varies.


Simple example:


In a population, there are blue pens and red pens
Reproduction is asexual and blue pens create other blue pens while red pens create other red pens.
blue pens make more offspring than red pens.


In such a situation, natural selection occurs yielding the frequency of the blue pens to increase in the population while the frequency of red pens will decrease.

Natural Selection

Natural Selection is the process by which variants of genes called alleles are selected and therefore increase in frequency. This selection result from a differential reproductive success.

Mutations

In the broad sense mutation is any change in the DNA sequence. Some changes are more likely to happen than other but in any case, the likeliness of these changes to happen is not dependent on the consequence they will have on the phenotype (shortly speaking, a phenotype is how an individual looks like) and on the reproductive success. So mutations occur randomly and the specific mutation that would be needed in the population may not occur. Therefore saying, if a trait is needed (in the sense of "if a trait would be beneficial"), then a mutation will occur to make this trait existing is wrong. Note that most mutations are deleterious (decrease the reproductive success) while few of them are beneficial (increase the reproductive success) and those that are beneficial are more likely to rise in frequency in the population.

Genetic drift

If the change in frequency of mutations would depend exclusively on natural selection, then I would not have said before that a beneficial mutation is more likely to raise in frequency but I would have said that a beneficial mutation will raise in frequency deterministically. An intuitive explanation of what is genetic drift can be found on this post. It will also allow you to understand why small population undergo a more random change in frequency of their genes than are big population.



Considering your opposing statements

Hopefully, the following is clear from the above discussion but I would like to directly address your statements.


  My friend said that Natural Selection is a mechanism inside the organism that mutates the DNA to make its offspring survive in an environment; that natural selection mutates the DNA beneficially and that random mutations are not useful (like blue eyes). But I disagree and think that it is closer to Lamarkian theory.


You are right that your friend is wrong!

It indeed sounds more or less Lamarkian. In any case, it is very wrong, as you said. Mutations are not caused deterministically under the pressure of natural selection to do specific things.

Are mutations completely random?

See Are mutations random?.

I do not want to go into too many complications. The sentence "mutations are random" is unclear. Does it mean that the mutation rate is random? Does it mean that the effect of a new mutation is random? And also the concept of randomness only make sense if we consider a set of a priori knowledge. So it is a little hard to fully answer this question and the easy, close-enough approximation for a starter in evolutionary biology is just to say that mutations are random (whatever that means). A slightly better approximation of reality is that mutation rate is an adaptive trait and can vary depending on the environment where the individual is found (adaptively or not). However, the effect of new mutations is really not deterministic. 

The mutation rate varies with the type of sequence considered. For example, a microsatellite sequence is a sequence or repeated DNA. For example AATAATAATAATAATAATAAT etc.. (note that the genetic code is written with 4 letters, A, T, C and G). Such sequences are highly mutable. So a mutation is more likely to occur in this region than in the middle of a coding region. And it is more likely for a mutation occurring in a coding region to affect fitness than for a mutation occurring in a microsatellite (it is possible that a mutation occurring in a microsatellite will affect fitness). 

Depending on the level of stress some organisms (plants mostly to my knowledge) can change their mutation rate. Consider for example an individual that is maladapted to its environment. If it mutates little, then the offspring will likely be as maladapted and in the long run, the lineage will disappear. If the individual is mutating a lot then, most offspring will have a very low fitness but eventually one will receive a beneficial mutation that will make it very strong and by itself, this offspring may save the lineage. This is what is called a bet-hedging strategy. The concept of bet-hedging can be summarized with the expression "Don't put all your eggs in the same basket".

You will note that the mutation rate is an evolving feature of an organism. This yield observation such as what is now called Drake's rule (original paper). Drake's rule indicates that the genome-wide mutation rate is always at the order of 1 (there is quite a bit of variation but it is a good approximation). 


  I told him that DNA from male and female recombines and randomly mutates making a new "recipe" for the offspring (adding a new characteristic(s)). If the offspring is well suited for the environment, then it survives and passes on its characteristics to its offspring. If it does not have fitness for its environment, it dies. So, Natural Selection is were nature "selects" who survives and reproduces a lot.


Sounds quite right!

You pretty much nailed it. Mutation adds genetic variation and natural selection selects from the available genetic variation. Your wording is a little uncommon though :). For example, an individual, it is incorrect to say that an individual has fitness or not. Each individual has a fitness, that is some value that encompasses both its fertility and survival probability. In a simple model, fitness is simply the expected number of offspring.

Note also, that the majority of mutations that affect the fitness of the individuals are not so much dependent on the details of the environment. Many mutations are just bad wherever you are. Think about a mutation that would reduce the efficiency of energy production (ATP in mitochondria). Such a mutation will be deleterious regardless of whether the weather is hot or cold for example.



Introductory course to evolutionary biology

You probably want to have a look at an introductory course to evolutionary biology such as Understanding Evolution.