To speed up things I implemented a makemove/undomove within the function
This will work fine, so long as you are doing depth-first search (which you are, because of the recursive calls).
due to the nature of Java not passing objects by reference
Typo? You mean Java always
passes by reference. So no new copy of an object is made by default.
and I don't pass the board object as a parameter to itself
This is a little confusing. Does it mean that the search function is within the board class itself? Or that a single static board object exists?
Regardless, I'd have player objects decide their own moves and have any search functions in their classes. These methods should pass a board around as a parameter.
All you need to do is put your move and undo-move before and after each recursive call, as in (pseudocode):
double search(Board board, int depth)
if( depth=0 )
maxValue = 0
for each move in children(board)
maxValue = max(maxValue,search(board,depth-1)