Afghanistan, Algeria, Iran, Iraq, Kuwait, Lebanon, Libya, Saudi Arabia, Somalia, Sudan, Syria, and Yemen block passports containing stamps or visas from Israel. If you intend to visit any of these nations, ask immigration to stamp a blank page, rather than your passport, when entering. Note that those countries will also search for Jordanian/Egyptian exit stamps from land borders with Israel and will likewise prohibit your entry if they find one.
Citizens from most European and North American countries as well as Argentina, Brazil, Singapore, Hong Kong, Australia, New Zealand, Philippines, Japan, South Korea, Ukraine and Russia do not need a visa prior to arrival. If however you are suspected of being of Arab decent, Muslim, a peace activist or missionary it is very possible that you will be subject to prolonged questioning, searches and or denied entry without explanation according to the US Department of State. Be aware that holding citizenship in one of the above listed countries does not guarantee entry. These decisions are left to the discretion of immigration officers. (http://www.mfa.gov.il/NR/...). Note that German citizens born before January 1, 1928, do have to apply for a visa in advance. This visa will be given if you were not heavily involved in events during the Nazi era and will be valid for the whole time your passport is valid. Further note that in some Arab states it constitutes a crime for their citizens to enter Israel at all. Even if you're an Arab-born citizen of a European or North American country having entered Israel may have consequences when returning to your country of birth.
Pay attention to the fact that many Arab and Islamic countries deny entry to any person that has been to Israel. If arriving by air or by sea and wishing to go to Arab states with the same passport, try asking the Israeli immigration officer to put their stamp onto a separate piece of paper. Depending on the current situation, they are often willing to do this. Then you're safe not to be denied entry by the Arab states named above. However, this may not be enough if you've entered Israel by land: in the most paranoid countries notably Syria and Lebanon, your passport will be scrutinized not only for Israeli stamps, but also neighboring countries' stamps from Israeli land border crossings like Taba Egypt and Arava/Aqaba Jordan. They will also check for luggage stickers or their residue which are stuck to the back of passports at Israeli border crossings. In this case, you'll have to apply for a second passport, which allows you to have an Israeli stamp in one passport and travel to the Arab states with another one. Inquire at your own embassy.
Israeli immigration may take a dim view of travelers arriving from Arab countries, but you are unlikely to face anything worse than very time-consuming, and repetitive, but polite questioning. Depending on the situation, if you have stamps from other Arab countries in your passport, you should expect to be taken to one side without any explanation and eventually questioned. This can take anywhere from 10 minutes to several hours. The key thing to remember is this: if you have nothing to hide, then, other than the inconvenience of questioning, you should have nothing to be worried about. If you are a young backpacker, especially if you travel alone, it is much more likely you will be detained for questioning in Tel Aviv airport. There is a "selection committee" of 2 security guards waiting when you go up the escalators from your flight, and if you seem suspicious they will not hesitate to stop you. If you dress up nicely, seem a part of another group or a family they are less likely to bother you.
If you're in Israel on a tourist visa B2 and decide to renew your visa for a longer term, you may do so at the Ministry of the Interior Visa office (http://www.mfa.gov.il/MFA...). In Tel Aviv, it's located on the 2nd floor at 125 Derech Menachem Begin. That office is open from 8AM - 12PM from Sunday through Wednesday. Alternately, citizens from most European and North American countries can renew their visas by crossing into Jordan and back at the Arava border crossing near Eilat or by crossing into Egypt and back at Taba.
It's surprisingly difficult to travel to Israel by boat. The main route is from Limassol in Cyprus to Haifa, and the main operators are Louis Cruises (http://www.louiscruises.com/) and Salamis Cruises (http://www.salamis-tours.com/). As the name says, these are cruise services and they do not advertise one-way fares, but they may be willing to carry you for around €150-170 if you're persistent and they have space -- showing up at the port office on the day of departure may work. Both companies seem to start and stop cruises on short notice, so enquire locally.
If you manage to hitch a lift on a freighter, Israel's major sea ports are Haifa and Ashdod. Private yachts use the marinas at Herzliya north of Tel-Aviv, Ashkelon South of Ashdod, Haifa and Tel Aviv.
See also: From Cairo to Jerusalem by bus
Daily direct buses are available from Amman to Tel Aviv, Haifa and Nazareth, via the King Hussein bridge. Call the operator +972-4-6573984 for details. Otherwise, you can take a taxi from the north bus terminal in Amman 5JD each for four people sharing: if you don't have a group, either wait for either people to arrive or pay 20JD and go yourself. After clearing Jordan customs, a separate JETT bus will take you across the border to Israeli customs for a small fee, then once past Israeli customs, a Palestinian bus company offers buses to Jericho and Ramallah. From Ramallah, a share taxi will take you to Jerusalem.
To get from Cairo to Israel by bus, or vice-versa, take a look at the From Cairo to Jerusalem by bus article.
If you have more money to spend, there are buses from Tel Aviv and Jerusalem US$95-110 one way to Cairo, operated by Matzada tours Tel 972-2-6235777 and Aviv tours Tel 972-36041811. You still have to change buses at the border.
Note: Use Matzada tours at your own risk! They subcontract the Egyptian side of the Journey and do little to nothing to help if there is any mix up. At least one Matzada group from Tel Aviv/Jerusalem reportedly was held at the Taba Border - Egyptian side for 7 hours due to the fact that the Israeli company failed to pay the Egyptian company.
There are land routes from both Egypt and Jordan to Israel. There are no land routes to either Syria or Lebanon, owing to the continuing state of hostilities with these countries. The border crossings have security measures similar to the airports.
Jordan has three crossings with Israel: the Allenby/King Hussein Bridge the shortest way between Amman and Jerusalem, the busiest crossing; the Jordan River in the north; and Arava/Yitshak Rabin 2 km from Eilat. If you ask the immigration officers Jordanian and Israeli politely they will usually stamp a separate piece of paper. It's fairly straightforward to cross using a series of buses. If you cross the King Hussein Bridge you will not be given an exit stamp for Jordan, and you will not be stamped on re-entry if you choose to return. If you request your Israeli stamp on a separate piece of paper, and have that paper stamped on the way out, you will have entered Israel with absolutely no evidence on your passport. Be advised, however, that requesting no permanent stamp in your passport is a "red flag" for the immigration staff, and you may be detained at the border and questioned, sometimes at length. If asked, it is best to justify your request by suggesting your wish to visit a non-Arab destination with Israel restrictions, such as Malaysia. Mentioning West Bank destinations in your itinerary will also arouse suspicion - it is just best to avoid mentioning Palestine at all while passing the border.
From Egypt you can cross the border at the Taba Border Terminal, near Eilat. From the terminal to Eilat, take bus number 15, or a taxi. The terminal is open 24 hours a day, 7 days a week, with the exception of Yom Kippur The Day of Atonement and the Muslim Feast of Sacrifice.
Israeli rental cars are not generally permitted across the borders for insurance reasons; in addition, it may not be advisable to travel in Arab countries while displaying an Israeli number plate.