Is every submodule of a projective module projective? 
Is every submodule of a projective module projective?  

I know that the answer is no, but I haven't been able to come up with any concrete examples despite quite a bit of effort.
 Also, if the question is changed to whether or not every submodule of a free module is projective,what happens then? Any suggestions would be appreciated.  
 A: A ring $R$ for which every submodule of a projective $R$-module is projective is called hereditary. If $R$ is not comutative, one distinguishes right and left hereditary rings. 
The ring $\mathbb{Z}/n\mathbb{Z}$ is hereditary (for $n\neq 0$) if and only if the integer $n$ is square-free; that is, $\mathbb{Z}/n\mathbb{Z}$ is a direct product of fields. 
For the second question, see here.
A: Let $k$ be a field. The ideal
$$(x_1, x_2) =x_1 k[x_1,x_2] + x_2 k[x_1, x_2]\subset k[x_1, x_2]$$
is not a projective $k[x_1, x_2]$ module. 
It's enough to check that $(x_1, x_2)$ is not invertible see http://en.wikipedia.org/wiki/Fractional_ideal#Definition_and_basic_results .
Remark: In fact that every finitely generated projective module over $k[x_1, \ldots, x_n]$ must be free : http://en.wikipedia.org/wiki/Quillen%E2%80%93Suslin_theorem
A: Since any projective module is a submodule (even a summand) of a free module, the two formulations of your questions are equivalent.
A ring $R$ which has the property that any submodule of a projective $R$-module 'inherits'  projectivity is called hereditary. This is equivalent to saying that the global dimension of $R$, $$\text{gldim}(R\text{-Mod}) := \text{sup}\{k\ |\ \text{Ext}^k_R(-,-)\not\equiv 0\},$$ is at most $1$, so $\text{Ext}^k_R(M,N)=0$ for all $k\geq 2$ and all $R$-modules $M,N$.
I will try to give some intuition for this in the contexts of geometry and representation theory:
Geometry
In commutative algebra and algebraic geometry, the finiteness of the global dimension is a homological way to express regularity/smoothness:

Serre's Theorem 
If $(R,{\mathfrak m},k)$ is a local Noetherian ring, then the following are equivalent:
  
  
*
  
*$R$ is regular, i.e. $\text{dim}_k({\mathfrak m}/{\mathfrak m}^2)=\text{dim}(R)$.
  
*$\text{gldim}(R\text{-Mod})<\infty$.
  
  
  In case the two equivalent conditions are met, $\text{gldim}(R\text{-Mod})=\text{dim}(R)$.

Hence, you will get lots of examples by looking at non-regular local rings, of which there are plenty, e.g. any local ring with zero divisors will do:
Example Let $k$ be a field, and put $R := k[\varepsilon]/(\varepsilon^2)$. Then $\text{dim}(R)=0$, but $\text{dim}_k{\mathfrak m}/{\mathfrak m}^2=1$, so $R$ is not regular. We therefore must have infinite global dimension, and in particular non-projective submodules of free modules. And indeed, $k\cong k\cdot\langle x\rangle\subset R$ is not projective, since the quotient map $R\to R/{\mathfrak m}=k$ does not split.
Representation Theory
In the representation theory of finite-dimensional algebras, hereditary algebras occurr as path-algebras of acyclic quivers without relations (this means that you fix a finite graph without oriented cycle and look at the category of configurations of vector spaces where at each vertex of the graph you put a vector space and at each oriented edge you put a homomorphism of vector spaces - similar to the representation theory of the commutative square below). Adding relations, however, will produce non-hereditary algebras. 
Example Consider the representation theory of the commutative square, i.e. pick $R$ such that $R\text{-Mod}$ is equivalent to the category of diagrams of vector spaces $$\begin{array}{ccc} V_{00} & \stackrel{\alpha}{\to} & V_{01}\\ {\scriptsize\beta}\downarrow & & \downarrow{\scriptsize\gamma} \\ V_{10} & \stackrel{\delta}{\to} & V_{11}\end{array}$$ satisfying $\gamma\alpha=\delta\beta$. Then the module $$\begin{array}{ccc} k & \stackrel{1}{\to} & k\\ {\scriptsize 1}\downarrow & & \downarrow{\scriptsize 1} \\ k & \stackrel{1}{\to} & k\end{array}$$ is projective (it represents the exact functor $V_{\ast\ast}\mapsto V_{00}$), but its submodule $$\begin{array}{ccc} 0 & \stackrel{0}{\to} & k\\ {\scriptsize 0}\downarrow & & \downarrow{\scriptsize 1} \\ k & \stackrel{1}{\to} & k\end{array}$$ is not: it represents the pullback functor $$V_{\ast\ast}\mapsto \{(v,v^{\prime})\in V_{01}\oplus V_{10}\ |\ \gamma(v)=\delta(v^{\prime})\}$$ which is not exact (not even the kernel functor, which is obtained by restriction to representations with $V_{00}=V_{10}=0$, is exact; see http://en.wikipedia.org/wiki/Snake_lemma)
