How exactly does heterozygous sickle trait help patients survive malaria
Sickle cell anemia is characterized by the formation of sickle shaped red blood cells rather than the usual biconcave ones. For a double recessive homozygous genotypic person, i.e. an infected person, this causes severe lack of oxygen diffusion into the RBCs because of defective haemoglobin production.
In case of a carrier, he/she carries the gene for the defective version of haemoglobin but does not show the symptoms for the disease. 

The malarial agent, Plasmodium uses haemoglobin, or more specifically haem as its main nutrient source The defective sickle haemoglobin induces the expression of heme oxygenase-1 (HO-1) enzyme in hematopoietic cells (those which produce erythrocytes, for example marrow of long bones). Carbon monoxide (CO), a byproduct of heme catabolism by HO-1, prevents further accumulation of circulating free heme after the infection by Plasmodium. This decreases the pathogenicity of the organism and prevents the disease from occuring.  Moreover, sickle haemoglobin inhibits activation and/or expansion of T lymphocytes (specifically CD8+T cells), which recognize the antigens expressed by Plasmodium and hence do not attack it. This is an immunoregulatory effect that does not involve the heme oxygenase enzyme. 
This leads to the carrier person having innate resistance to malaria (or at least Experimental Cerebral Malaria )

And no, the RBC itself is not structurally different. Though there might be some
sickle shaped RBCs in the blood, their number is very less. The major difference comes from the haemoglobin in the red blood cell.

Here is the original paper which explains the phenomenon in detail.