RuleDelayed

lhs :> rhs can be used in replacement functions to say that instances of lhs should be replaced with rhs, evaluating rhs only after replacement.

Attributes[RuleDelayed] := {HoldRest, Protected, SequenceHold}

Simple examples

In[1]:= ((2^(x^2 + 1) + x^2)) /. (((x^2) :> y))
Out[1]= 2^(y + 1) + y

To demonstrate the difference between Rule and RuleDelayed:

In[2]:= Apply[Equal, ({1, 1}) /. ((1 -> RandomReal[]))]
Out[2]= True

In[3]:= Apply[Equal, ({1, 1}) /. ((1 :> RandomReal[]))]
Out[3]= False