IANAL, but I don't think the executive branch has the authority to do what the petition is asking. The patent office merely interprets what Congress and the courts tell it - while there is some interpretational discretion, I don't think it extends to the point of rejecting all software patents and certainly not to the point of retroactively invalidating all of them.
The President can certainly sign an executive order saying pretty much whatever he wants to say. The President doesn't really have any explicit authority to issue executive orders, but historically executive orders are treated the same as Congressional legislation (although the courts can certainly overturn one).
That said, I would much prefer a proper legislative approach to an executive one. The Patent and Trademark Office is part of the Department of Commerce, so I don't think it would be frowned upon too much for the executive branch to enact some reform. Still, I think a legislative approach would be more robust and less controversial.
Yes, the President can issue orders to them. But if those orders countermand the direction and mandate the patent office receives from congress as interpreted by the courts, the executive branch has overstepped its authority. Such an order would be, in my opinion, an order to step outside authority and outside law. Yes, such orders have been given on many occasions, but that doesn't make them right.
