Many go for a weekend a month in advance, and look at the "For Rent" signs, then make a deal with the homeowner (usually haggling on price). That is of course not very practical for someone from the U.S. !!
Punta del Este is nice (though some people like other kinds of vacations, like Punta del Diablo), but it's very expensive (even for people from the U.S.), especially in January. December is a little cheaper.
The times I've been there I went to a hostel. My parents use the "haggling" option, so I don't have a good recommendation for online search. Airbnb is slightly more expensive than the average listing, but not by much.
