[Before reading this post, see this updated post.]
Governor Palin could appoint someone to fill the remainder of Senator Stevens’ term, which runs until January.
Here is the relevant portion of the Alaska Code:

Sec. 15.40.010. Conditions and time of filling vacancy by appointment and special election.
When a vacancy occurs in the office of United States senator, the governor, at least five days after the date of the vacancy but within 30 days after the date of the vacancy, shall
(1) appoint a qualified person who, if the predecessor in office was nominated by a political party, has been, for the six months before the date of the vacancy, and is, on the date of appointment, a member of the same political party as that which nominated the predecessor in office to fill the vacancy temporarily until the vacancy is filled permanently by election; and
(2) by proclamation and subject to this chapter, call a special primary election and a special election to fill the vacancy for the remainder of the term of the predecessor in office if the predecessor’s term would expire more than 30 calendar months after the date of the vacancy.

Here is the provision that seems to apply if Senator Stevens withdraws from running in the general election:

Sec. 15.25.200. Withdrawal of candidate’s name.
If a candidate nominated by petition dies or withdraws after the petition has been filed and 48 days or more before the general election, the director may not place the name of the candidate on the general election ballot.

The statute is silent as to what happens in fewer than 48 days. A similar issue arose in New Jersey when Sen. Torriicelli withdrew close to the election—but not as close as this is to election day–but the New Jersey Supreme Court, facing a statute that expressly gave the parties the right to name a replacement if there was enough time–gave the Democrats a chance to name Torricelli’s replacement. Hard to see any of this happening before election day now, given that Alaskans are already voting on absentee ballots; in New Jersey, ballots had not yet been printed.
CQ notes the rules on Senate expulsion, should Senator Stevens be reelected.
Fnally, Politico notes that it is not clear whether Sen. Stevens, if he stays on the ballot, retains the right to vote for himself.
UPDATE and CORRECTION: Dan Lowenstein points me to the New Jersey’s Supreme Court opinion in the Samson case. The opinion confirms, as Dan remembered and I misremembered, that some absentee ballots had in fact gone out in the New Jersey race. (A snippet from the opinion: “In respect of absentee voters, particularly military and civilian New Jersey citizens dwelling abroad, we are informed that of approximately 19,000 absentee ballots authorized as of October 2, 2002, some 1,700 had been mailed and few had been returned. “)