When we lift an object with constant velocity the work done by us is mgh
Yes, when you lift a brick you do work on it. You add energy to it. You increase its mass. Its mass-energy is increased, and we call the extra energy gravitational potential energy. It's important to note that it isn't in "the system", it's in the brick.
You can work this out if you imagine throwing a brick upwards. Momentum is equal and opposite, such that p1=m1v1 = p2=m2v2 where m1 is the mass of the Earth and m2 is the mass of the brick. However KE=½mv² so KE1 ≠ KE2. The Earth doesn't move in any noticeable way, so the brick gets just about all of the kinetic energy. As the brick slows down this is converted into potential energy. But again, it's in the brick. If you throw your brick upwards at 11.7 km/s, the brick along with all the energy you gave it leaves the system forever. Because 11.7 km/s is escape velocity.
and that by gravity is -mgh.
Gravity doesn't actually do any work on a body. We call it a force, but it isn't a force in the Newtonian sense. Imagine you threw the brick upwards at 10m/s giving it some kinetic energy. Gravity converts the kinetic energy into potential energy, which is mass-energy, such that at the highest point the brick is momentarily motionless, and its mass-energy is at a maximum. Then as it falls gravity converts some of this mass-energy into kinetic energy. When the brick hits the ground this kinetic energy is dissipated, and the brick is left with a mass deficit. See the Wikipedia binding energy article. When you separate two bodies you increase their mass. When one's smaller than the other, you increase the mass of the smaller body more.
The potential energy gained will come from the work done (PE=mgh).
That's right. When you lift the brick you do work on it and you increase its mass.
But how can the object gain potential energy if the net work done is zero?
It isn't zero.
If work by us is converted into potential energy then what is the effect of work done by gravity, where does it go?
The work done by us in lifting the brick goes into the brick. When it falls down gravity doesn't do any work, it just converts mass-energy aka potential energy into kinetic energy. When this is dissipated you're left with a mass deficit.