how to use transition in CSS and HTML

Unfortunately we can't animate (or set) the width of a border. So we'll need another way.

With CSS you can create pseudo-elements, like ::before and ::after to create blocks inside of another element. For your case we can use either of the aforementioned pseudo-elements to create a border like bar at the bottom of each li.
This bar can then be animated like a regular HTML element. This means that we can change the width, height, color, etc, but still make it look like a border.

In the example below I've used the ::after psuedo element on your li elements to create the border like element in your list items. I've use ::after because the border needs to be after the content in the li.

The element starts with a scaleX transformation which manipulates the horizontal size of the pseudo-element. Whenever you hover, the scaleX is restored to the full width.
The reason for using transform instead of width is that transform is optimized for transitions and animations, though there is no law against transitioning width instead.

body {
  background-color: gray;
  font-family: 'Gill Sans', 'Gill Sans MT', Calibri, 'Trebuchet MS', sans-serif;
}

ul {
  list-style-type: none;
  margin: 0;
  padding: 0;
  overflow: hidden;
  background-color: #333;
  border-radius: 50px;
  width: 90%;
}

li {
  /**
   * This needs to be position: relative so that the ::after element
   * will stay be relative to the size of this element.
   * Try to remove it and see what happens.
   */
  position: relative;
  float: left;
  transition: border-color 0.2s;
}

li:hover {
  background-color: rgb(43, 43, 43);
}

li a {
  display: block;
  text-decoration: none;
  color: rgb(255, 255, 255);
  text-align: center;
  padding: 15px 20px;
}

li::after {
  content: "";
  display: block;
  position: absolute;
  bottom: 0;
  left: 0;
  height: 3px;
  width: 100%;
  transform-origin: right center;
  transform: scaleX(0);
  transition: transform 0.2s;
  background-color: white;
  z-index: 1;
}

li:hover::after {
  transform: scaleX(1);
}

.searchbtn {
  float: right;
}

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link rel="stylesheet" href="style.css">
  <script src="script.js"></script>
  <title>Title</title>
  <link rel="icon" type="icon/x-type" href="IMG/fav.png">
</head>

<body>
  <ul>
    <li><a href="#">Home</a></li>
    <li><a href="#">About</a></li>
    <li><a href="#">Support</a></li>
    <li class="searchbtn"><a href="#">Search</a></li>
  </ul>
</body>

</html>

On a sidenote: you're using some old techniques, like float, to position your elements. These techniques have been surpassed by Flexbox and CSS Grid Layout which give you more (and better) control over layouts. So I'd recommend that you study the two links above and find a more up-to-date tutorial (YouTube is covered in them about Flexbox and Grid) on creating layouts.

The transition to the width is not doing anything because you are never changing the width of the "li" element. The way the "transition" property works is by animating changes in the property you select. If you want to change the text color on hover and have a nice transition, you could do something like this:

span {
  color: #000;
  transition: color 0.2s;
}

span:hover {
  color: #ccc;
}

I think you could use the "after" pseudo selector to achieve what you want by emulating a bottom border. Since you can't modify the length of the border directly.

Here's a working example