> When work is done, the energy is stored either in form of potential or
> kinetic.

Just to be clear, it is an inclusive "or".  When work is done all the energy may be stored as potential energy, or it may be stored partly as potential and partly as kinetic energy, or it may be stored completely as kinetic energy, as illustrated in the following 3 scenarios that may help you in answering your questions.

***Scenario 1***: A net constant horizontal force $F$ is applied to an object thorough a horizontal distance $d$ in the absence of friction in the Earth's gravitational field. The net work $Fd$ will equal the change in kinetic energy $\Delta KE$. All of the work done is stored as kinetic energy and none as gravitational potential energy. I realize this is not the situation you are talking about, but I mention it only because of the generalization implied by your introductory statement. 

***Scenario 2:***  An object initially at rest on the ground is raised and brought to rest at a height $h$ above the ground. The net change in kinetic energy is zero. All the work is stored as potential energy. To make this happen, initially, an upward force greater than $mg$ is needed to give it an initial acceleration to start it moving upward. So it initially acquires kinetic energy. Then let the force be quickly reduced to exactly equal $mg$. Now the net force is zero, but the object continues to move up at constant velocity. 

Before reaching height $h$ the upward force is reduced to less than $mg$ so that the object decelerates and comes to rest exactly at height $h$. It has lost kinetic energy exactly equal to what it initially acquired by the time it reaches the height $h$. The overall change in kinetic energy is therefore zero. But the change in potential energy is $mgh$. All of the work done is stored as gravitational potential energy. 

***Scenario 3:***  Same as scenario 2 except that before reaching $h$ *the force is not reduced* so that the object continues to have a constant velocity $v$ when it reaches $h$. In this case, when the object reaches $h$, it has both stored potential energy $mgh$ and stored kinetic energy $\frac{mv^2}{2}$.

Given the above, in answer to your specific questions:

> If the box was initially stationary, with application of that force,
> the net force will be 0 thus the box will remain stationary with no
> change in potential energy.

Correct. If the upward applied force equals, but never exceeds $mg$, it will never acquire an upward acceleration to start it moving. In order to start upward movement, the upward force must at least momentarily exceed $mg$ to give it an initial acceleration. Once in motion, the upward force can be reduced to equal $mg$ and the box will continue to move up at constant velocity. This is scenario 2 above.

> But if the box initially had some velocity, with application of 𝑚𝑔
> upwards, the net force will be 0 again but this time the box will be
> constantly moving up. If the box constantly moves up, it will be
> gaining potential energy as well.

Correct, but only if initially the upward force was greater than $mg$, even if briefly, in order to get the box moving. This is analogous to scenario 3 above. The box has acquired kinetic energy based on at least a momentary upward force of greater than $mg$ to get it started. With the velocity constant, its kinetic energy is constant. But it continues to acquire potential energy as it moves upward as long as the upward force equals the downward force of gravity so that it maintains its constant velocity when it reaches height $h$. 

> It requires same amount of energy to generate 𝑚𝑔 upwards but in the
> first case, no energy is stored while in the second, some energy is
> being stored. So whats going on in this case? Thanks

Based on the above you should now realize that an initial upward force greater than $mg$ is necessary to get the box moving and do work. Energy does not create $mg$ upward because $mg$ upward is a force, not energy. Energy is involved only if $mg$ upwards causes movement of the box. And that only happens if there is initially a net upward force to get the box moving, that is, only if the initial upward force momentarily exceeds $mg$.

Hope this was not too long and helped.