Does the mass increase or decrease here? I am very very newbie in Special Relativity.
But consider this situation. Lets say I have a block of mass $m$ which is at rest relative to a certain inertial frame of reference. Let's say I hit this block and give a velocity $\frac{c}{2}$. There are two observers, one is at rest and one is moving with a velocity of $\frac{c}{2}$. I'll call the observer at rest as Observer A and the other as Observer B.
Observer A:
He/She observed the block to move from zero to a speed of $\frac{c}{2}$. As a newbie I may be, I do know that mass increases by a factor of $\gamma$, and that's:
$$\gamma=\frac{1}{\sqrt{1-\frac{v^2}{c^2}}}$$
In his/her case, $\gamma =\frac{2}{\sqrt{3}}$.
The block will increase in mass by a factor of $\gamma$.
Observer B:
This observer would see the block moving with $\frac{c}{2}$. This observer would see that the mass of the object decreased by a factor of $\gamma$.
Both can't be true at the same time. This seems to be a paradox. All inertial frames are equivalent, that's a postulate of General Relativity I think. How would this be resolved?
 A: To be clear: one observer does observe the relativistic mass increasing, and another does observe the relativistic mass decreasing, but there is no contradiction.
Let's change perspective to avoid the notion of "relativistic mass". Denote the rest mass (aka "the mass") by $m_0$.  Denote the energy-momentum of the block as a vector $(E,p)$. 
Before hitting the block, observer A describes the block as having energy-momentum $(m_0 c^2,0)$. Observer B describes the block as having energy-momentum $(\gamma m_0 c^2,-\gamma m_0 \frac{c}{2})$.
After hitting the block, observer A describes the block as having energy-momentum $(\gamma m_0 c^2,\gamma m_0 \frac{c}{2})$. Observer B describes the block as having energy-momentum $(m_0 c^2,0)$. 
There is absolutely no paradox. All four cases let the energy-momentum vector have invariant interval $E^2-(pc)^2=(m_0 c^2)^2$. To get a paradox you have to speak in terms of some actual physical thing that happens. There is, however, a physical effect that occurs in special relativity and not in Newtonian mechanics. Imagine the situation after the block was hit, and imagine two possibilities:
If observer B were to hit the block again, they would supply a (relativistic) momentum $\Delta p_B$ and see a velocity change $\Delta v_B$. If observer A were to hit the block again, they would supply a (relativistic) momentum $\Delta p_A$ and see a velocity change $\Delta v_A$. If we imagine these two possibilities and demand that A and B both try to achieve the same change in velocity, then $\Delta v_A=\Delta v_B$, and in fact:
$$\frac{\Delta p_A}{\Delta v}<\frac{\Delta p_B}{\Delta v}$$
Observer B finds it harder to increase the velocity than does observer A. The ratio of momentum over velocity has units of mass, so this is suggestive! I'm cheating though, because $\Delta p_B/\Delta v$ isn't actually the relativistic mass as it's normally defined*, but this is the basic phenomenon. Observer B finds it harder to increase the velocity by a fixed amount $\Delta v$ than observer A (who tries to increase the velocity by the same amount $\Delta v$). In fact, if observer B tried to increase the velocity in its frame by another $c/2$, they would find it impossible. Observer A, on the other hand, can easily increase the velocity in its frame by another $c/2$. This is what is meant by the statement that the relativistic mass increasing. These two things correspond to two different physical situations, and so there is no contradiction at all.
*(this is $dp/dv$, but $p=\gamma m_0 v=m_\text{rel}v$ [by the definition of $m_\text{rel}$], so $\frac{dp}{dv}=m_\text{rel}+v \frac{d m_\text{rel}}{dv}$ by the product rule.)
